Start learning free

LESSON 259 OF 671 · NESTED LOOPS OVER GRIDS

Diagonal Sum in JavaScript: One Loop, Two Indices

Practice Read the full explanation

Given a square grid of integers grid, with as many rows as columns, return the sum of the cells on its diagonal: the cells that go from the top-left corner to the bottom-right corner.

A grid is an array of rows, and each row is an array of integers. Rows are numbered from 0, top to bottom, and columns from 0, left to right. A cell is on the diagonal when its row number and its column number are the same: row 0 and column 0, row 1 and column 1, and so on.

 

Example 1:

Input: grid = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
Output: 15
Explanation: The diagonal cells are 1, 5 and 9: 1 + 5 + 9 = 15.

Example 2:

Input: grid = [
  [7]
]
Output: 7
Explanation: A grid with one cell: that cell is the whole diagonal.

Example 3:

Input: grid = [
  [-1, 2],
  [3, -4]
]
Output: -5
Explanation: The diagonal cells are -1 and -4: -1 + (-4) = -5. The 2 and the 3 are not on the diagonal.

 

Constraints:

  • grid has n rows and n columns, with n at least 1.
  • Every value is an integer between -1000 and 1000; values can be negative.
STEP 1 OF 4
    Ctrl + Enter to check

    JAVASCRIPT · NESTED LOOPS OVER GRIDS

    Diagonal Sum in JavaScript, explained

    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

    1. Declare total with let and start it at 0. It is let because it grows in the loop.
    2. Loop over i from 0 while i < grid.length. Each turn handles one row, and therefore one diagonal cell.
    3. Add the diagonal cell. total += grid[i][i]. The first [i] picks row i, and the second picks column i inside that row.
    4. Return total after 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: reading grid[i][i] past the end of a row gives undefined and turns the total into NaN.

    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]] gives 15.
    • grid = [[7]] gives 7.
    • grid = [[-1, 2], [3, -4]] gives -5.
    Keep going with JavaScript650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free