Sum of Both Diagonals
EasyMatrixFree
Problem
A square tiled floor is described by an n × n grid of tile weights. A decorator lays a stripe along both diagonals: the main diagonal from top-left to bottom-right and the anti-diagonal from top-right to bottom-left.
Return the total weight of the tiles covered by at least one stripe. When n is odd the two stripes cross at the centre tile, which must be counted only once.
Example 1
- Input:
- grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
- Output:
- 25
Main diagonal 1 + 5 + 9 = 15, anti-diagonal 3 + 5 + 7 = 15; the shared centre 5 is counted once: 15 + 15 - 5 = 25.
Example 2
- Input:
- grid = [[2, 1], [1, 2]]
- Output:
- 6
With an even size the diagonals share no tile: 2 + 2 + 1 + 1.
Example 3
- Input:
- grid = [[5]]
- Output:
- 5
Constraints
- 1 ≤ n ≤ 1000
- -10^4 ≤ grid[i][j] ≤ 10^4
Hint
Show the first hint
Which cells lie on the main diagonal? Which lie on the anti-diagonal? Write both as a formula in the row index.
Walkthrough
How to approach it
01Clarify before coding
- Is the grid always square? Yes, n × n.
- Is the centre counted twice when n is odd? No, once.
- Can weights be negative? Yes, so do not assume the total grows.
02Brute force
Scan all n² cells and add those with r == c or r + c == n - 1.
Cost: O(n²) time, O(1) space: correct, but it visits a million cells for n = 1000 when only 2n matter.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.