Rectangle sum queries
You are given a rectangular grid of integers (a non-empty list of equal-length rows) and a batch of rectangle queries. Each query is [r1, c1, r2, c2] with 0 <= r1 <= r2 and 0 <= c1 <= c2, all inside the grid, and asks for the sum of every cell in that inclusive rectangle. Return the answers in order, computing each query in constant time after preprocessing. Example: grid = [[1, 2], [3, 4]], queries = [[0, 0, 1, 1], [0, 1, 1, 1]] gives [10, 6].
Implement
rectangle_sums(grid: list[list[int]], queries: list[list[int]]) → list[int]Examples
in
[[[1,2],[3,4]],[[0,0,1,1],[0,1,1,1]]]out[10,6]What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 17 min
solution.py
InputExpectedGot
[[[1,2],[3,4]],[[0,0,1,1],[0,1,1,1]]][10,6]not run yetsample