Rectangle Totals on Demand
MediumMatrix
Problem
A solar farm reports the output of each panel on an m × n grid. Analysts send many queries, each asking for the total output of an axis-aligned rectangle of panels.
Each query is [r1, c1, r2, c2], the top-left and bottom-right corners (inclusive, r1 ≤ r2, c1 ≤ c2). Return the answers in query order. Answer each query in O(1) after preprocessing.
Example 1
- Input:
- grid = [[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]], queries = [[2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
- Output:
- [8, 11, 12]
The first rectangle covers rows 2–4 and columns 1–3: 2 + 0 + 1 + 1 + 0 + 1 + 0 + 3 + 0 = 8.
Example 2
- Input:
- grid = [[1, 2], [3, 4]], queries = [[0, 0, 1, 1], [0, 1, 0, 1], [1, 0, 1, 0]]
- Output:
- [10, 2, 3]
Constraints
- 1 ≤ m, n ≤ 200
- -10^4 ≤ grid[i][j] ≤ 10^4
- 1 ≤ queries.length ≤ 10^4
- 0 ≤ r1 ≤ r2 < m, 0 ≤ c1 ≤ c2 < n
Hint
Show the first hint
Summing each rectangle directly costs up to m · n per query. What could you precompute once?
Walkthrough
How to approach it
01Clarify before coding
- Are the corners inclusive? Yes, both corners belong to the rectangle.
- Does the grid change between queries? No, it is static, so preprocessing pays off.
- Can values be negative? Yes; the formula is pure arithmetic, so that is fine.
02Brute force
For each query, loop over its rows and columns and add the values.
Cost: O(q · m · n) in the worst case: 10^4 queries over a 200 × 200 grid is 4 · 10^8 additions.
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.
This problem is part of Pro.