Range Sum Query 2D - Immutable - Practice Coding Problems

Range Sum Query 2D - Immutable - Problem

Given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

You must design an algorithm where sumRegion works in O(1) time complexity.

Input & Output

Example 1 — Basic Rectangle Query

$ 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]

💡 Note: Query 1: Sum of rectangle from (2,1) to (4,3) = 2+0+1 + 1+0+1 + 0+3+0 = 8. Query 2: Sum from (1,1) to (2,2) = 6+3 + 2+0 = 11. Query 3: Sum from (1,2) to (2,4) = 3+2+1 + 0+1+5 = 12.

Example 2 — Single Cell Query

$ Input: matrix = [[1,2],[3,4]], queries = [[0,0,0,0],[1,1,1,1]]

› Output: [1,4]

💡 Note: Query single cells: matrix[0][0] = 1 and matrix[1][1] = 4.

Example 3 — Full Matrix Query

$ Input: matrix = [[1,2],[3,4]], queries = [[0,0,1,1]]

› Output: [10]

💡 Note: Sum of entire 2x2 matrix: 1+2+3+4 = 10.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 200
-10⁵ ≤ matrix[i][j] ≤ 10⁵
1 ≤ queries.length ≤ 10⁴
0 ≤ row1 ≤ row2 < m
0 ≤ col1 ≤ col2 < n

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D matrix with rectangle query bounds

Build Prefix Sum

Pre-compute cumulative sums for instant queries

Query Results

Answer any rectangle sum in O(1) time

Key Takeaway

🎯 Key Insight: Pre-computing 2D prefix sums transforms expensive O(mn) rectangle queries into instant O(1) calculations

Asked in

G Google 45 a Amazon 35 f Facebook 30 M Microsoft 25

The key insight is to pre-compute a 2D prefix sum array where each cell contains the sum from (0,0) to that position. Any rectangle query can then be answered in O(1) time using the inclusion-exclusion principle. Best approach is 2D Prefix Sum. Time: O(1) per query, Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Direct Sum	O(mn)	O(1)	For each query, iterate through all cells in the rectangle and sum them up
2D Prefix Sum	O(1)	O(mn)	Pre-compute cumulative sums to answer any rectangle query in O(1) time

Brute Force - Direct Sum — Algorithm Steps

For each sumRegion query, iterate through rows from row1 to row2
For each row, iterate through columns from col1 to col2
Add each matrix[i][j] to the running sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Rectangle

Identify the rectangle bounds (row1,col1) to (row2,col2)

Iterate Cells

Loop through each cell and add to sum

Return Sum

Return the accumulated total

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int matrix[][5], int rows, int cols, int queries[][4], int numQueries, int* results) {
    for (int q = 0; q < numQueries; q++) {
        int row1 = queries[q][0], col1 = queries[q][1];
        int row2 = queries[q][2], col2 = queries[q][3];
        int total = 0;
        
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                total += matrix[i][j];
            }
        }
        results[q] = total;
    }
}

int main() {
    int matrix[5][5] = {{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}};
    int queries[3][4] = {{2,1,4,3},{1,1,2,2},{1,2,2,4}};
    int results[3];
    
    solution(matrix, 5, 5, queries, 3, results);
    
    printf("[");
    for (int i = 0; i < 3; i++) {
        printf("%d", results[i]);
        if (i < 2) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Each query requires iterating through up to m×n cells in the rectangle

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track the sum

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Direct Sum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler