Command Palette

Search for a command to run...

Hectal
Problem 5.7 · Prefix SumMedium

Range Sum Queries on a Grid

PatternPrefix Sum

What it teaches: 2D prefix sums: any rectangle's sum with four lookups using inclusion-exclusion.

Practise it on judges as “Range Sum Query 2D - Immutable”.

The problem

Given a matrix and a list of queries [row1, col1, row2, col2], return the sum of each rectangle with top-left (row1, col1) and bottom-right (row2, col2).

Example 1

Input: matrix = [[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]

Constraints

  • 1 ≤ rows, cols ≤ 200
  • Up to 10⁴ queries

Pattern clues in the wording

  • → Many rectangle-sum queries on a fixed grid
  • → 2D version of range sums

These clues point to Prefix Sum: Store running totals so the sum of any range is one subtraction: prefix[r + 1] - prefix[l].

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int[] regionSums(int[][] matrix, int[][] queries) {
        int[] out = new int[queries.length];
        return out;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
matrix = [[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]]
[8,11,12]
2
matrix = [[7]]
queries = [[0,0,0,0]]
[7]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: 2D prefix sums · O(R·C + q)
1

Optimal: 2D prefix sums

Time O(R·C + q) Space O(R·C)

Build an (R+1) × (C+1) table once in O(R·C). Each query is P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1].

Approach 1
class Solution {
    public int[] regionSums(int[][] matrix, int[][] queries) {
        int R = matrix.length, C = matrix[0].length;
        int[][] P = new int[R + 1][C + 1];
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                P[r + 1][c + 1] = matrix[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
        int[] out = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int r1 = queries[i][0], c1 = queries[i][1], r2 = queries[i][2], c2 = queries[i][3];
            out[i] = P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
        }
        return out;
    }
}

Verdict: Constant time per query.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single-cell rectangle
  • Whole grid
  • Rectangle touching row 0 or column 0

Mistakes people make

  • Forgetting the + P[r1][c1] corner.
  • Mixing (row, col) order in queries.

Interview

Follow-up questions

What if cells can be updated?