Problem overview
The method diagonalSum(grid) receives a square grid of integers, with as many rows as columns, and returns the sum of the cells on the diagonal that goes from the top-left corner to the bottom-right corner. A cell is on this diagonal when its row number and column number are the same: row 0 and column 0, row 1 and column 1, and so on.
For [[1, 2, 3], [4, 5, 6], [7, 8, 9]] the diagonal cells are 1, 5 and 9, and the answer is 15. For [[7]] the single cell is the whole diagonal, so the answer is 7. For [[-1, 2], [3, -4]] the diagonal cells are -1 and -4, so the answer is -5, and the 2 and the 3 are not counted.
Approach
With grids, a nested loop is the habit, but here it would be wasteful. A diagonal cell has the same number for row and column, so one index i gives both: the cells are grid[0][0], grid[1][1], grid[2][2] and so on. A single loop over i reaches every diagonal cell directly.
A nested loop would also give the right answer, if you added a cell only when row === col. It would visit every cell and ignore all but one per row, which is much more work for the same result. Using the structure of the problem to skip the cells you don't need is the lesson's idea.
The loop runs grid.length times, one turn per row. In a square grid that is also the number of columns, so i never goes past the last column either.
Step by step
- Declare
totalwithletand start it at 0. It isletbecause it grows in the loop. - Loop over
ifrom 0 whilei < grid.length. Each turn handles one row, and therefore one diagonal cell. - Add the diagonal cell.
total += grid[i][i]. The first[i]picks rowi, and the second picks columniinside that row. - Return
totalafter the loop, when every diagonal cell has been added.
The solution in JavaScript
class Solution {
diagonalSum(grid) {
let total = 0;
for (let i = 0; i < grid.length; i++) {
total += grid[i][i];
}
return total;
}
}
Details worth knowing:
- A classic index loop.
for (let i = 0; i < grid.length; i++)is the pattern when you need the number of the turn, not just the item. grid[i][i]chains two lookups.grid[i]is a row, an array, and the second brackets index into that row.- The input must be square. The lesson promises it. For a grid with more columns than rows the diagonal would stop early, and for one with fewer columns the lookup would hit
undefined: readinggrid[i][i]past the end of a row givesundefinedand turns the total intoNaN.
Complexity
Time: O(n) for an n by n grid. The loop makes n turns, and each does one addition. A nested loop over all cells would be O(n²).
Space: O(1). Only total and i are stored.
Edge cases and common mistakes
- A one-cell grid.
[[7]]runs the loop once and returns 7. - Negative values. They are added like any others: for
[[-1, 2], [3, -4]]the result is -5. - Using the wrong diagonal. The other diagonal, from top-right to bottom-left, is
grid[i][grid.length - 1 - i]. This lesson asks for the top-left to bottom-right one. - Adding the whole row.
total += grid[i]adds an array to a number, which gives a string instead of a sum. - Starting at 1. Indexing starts at 0, so a loop starting at 1 skips the first diagonal cell.
- Returning inside the loop. It would stop after one cell.
Testing
grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]gives15.grid = [[7]]gives7.grid = [[-1, 2], [3, -4]]gives-5.
