Range Sum Query 2D - Immutable

Medium
2049.

Range Sum Query 2D - Immutable

Range Sum Query 2D - Immutable is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google and Meta interviews.

Given a 2D integer matrix that never changes, answer many queries asking for the sum of the elements inside a rectangle. Write the class NumMatrix:

  • NumMatrix(int[][] matrix) initialises the object with matrix.
  • int sumRegion(int row1, int col1, int row2, int col2) returns the sum of the elements in the rectangle whose upper-left corner is (row1, col1) and lower-right corner is (row2, col2), both included.

Each sumRegion call must take O(1) time.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input
["NumMatrix","sumRegion","sumRegion","sumRegion"] [[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
Output
[null,8,11,12]
Explanation
Rows 2–4 × columns 1–3 hold 2+0+1 + 1+0+1 + 0+3+0 = 8. The 2×2 block at rows 1–2, columns 1–2 is 6+3+2+0 = 11; rows 1–2, columns 2–4 sum to 12.

Example 2

Input
["NumMatrix","sumRegion","sumRegion","sumRegion"] [[[[-4,7],[2,-9]]],[0,0,1,1],[1,0,1,0],[0,1,1,1]]
Output
[null,-4,2,-2]
Explanation
The whole matrix sums to -4; the single cell (1, 0) is 2; the right column is 7 + (-9) = -2.

Constraints

  • m == matrix.length, n == matrix[i].length
  • 1 <= m, n <= 200
  • -10^4 <= matrix[i][j] <= 10^4
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • At most 10^4 calls are made to sumRegion
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
    
};

/**
 * @param {number} row1
 * @param {number} col1
 * @param {number} row2
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    
};

Sign in to run your own test cases

Sign in

Range Sum Query 2D - Immutable — Problem & Solution

Range Sum Query 2D - Immutable solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Range Sum Query 2D - Immutable is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Prefix Sum
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a 2D integer matrix that never changes, answer many queries asking for the sum of the elements inside a rectangle. Write the class NumMatrix:

  • NumMatrix(int[][] matrix) initialises the object with matrix.
  • int sumRegion(int row1, int col1, int row2, int col2) returns the sum of the elements in the rectangle whose upper-left corner is (row1, col1) and lower-right corner is (row2, col2), both included.

Each sumRegion call must take O(1) time.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
Output: [null,8,11,12]
Explanation: Rows 2–4 × columns 1–3 hold 2+0+1 + 1+0+1 + 0+3+0 = 8. The 2×2 block at rows 1–2, columns 1–2 is 6+3+2+0 = 11; rows 1–2, columns 2–4 sum to 12.

Example 2

Input: ["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[-4,7],[2,-9]]],[0,0,1,1],[1,0,1,0],[0,1,1,1]]
Output: [null,-4,2,-2]
Explanation: The whole matrix sums to -4; the single cell (1, 0) is 2; the right column is 7 + (-9) = -2.

Constraints

  • m == matrix.length, n == matrix[i].length
  • 1 <= m, n <= 200
  • -10^4 <= matrix[i][j] <= 10^4
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • At most 10^4 calls are made to sumRegion

Hints for Range Sum Query 2D - Immutable

  1. Hint 1

    In one dimension, a prefix sum array answers any range sum with one subtraction. Generalise the prefix to a rectangle anchored at the top-left corner.

  2. Hint 2

    Let P[r][c] be the sum of all cells above and to the left of (r, c) (exclusive). Build it with P[r+1][c+1] = matrix[r][c] + P[r][c+1] + P[r+1][c] - P[r][c].

  3. Hint 3

    A query is inclusion–exclusion: P[row2+1][col2+1] - P[row1][col2+1] - P[row2+1][col1] + P[row1][col1].

How to solve Range Sum Query 2D - Immutable

Precompute 2D prefix sums: P[r][c] is the sum of the rectangle from (0, 0) to (r - 1, c - 1). Any rectangle is then one big corner rectangle minus two strips plus the corner that was subtracted twice.

Approach

  1. Allocate P of size (m + 1) × (n + 1) filled with 0 (row 0 and column 0 are empty prefixes).
  2. For every cell: P[r+1][c+1] = matrix[r][c] + P[r][c+1] + P[r+1][c] - P[r][c].
  3. sumRegion(r1, c1, r2, c2) returns P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1].

Why it works

P[r2+1][c2+1] covers everything up to the bottom-right corner. Subtracting P[r1][c2+1] removes the rows above the rectangle and P[r2+1][c1] the columns to its left; the top-left block lies in both and was removed twice, so it is added back once. What remains is exactly the query rectangle. The same identity, read the other way, is the build formula.

Complexity

  • Time — O(m · n) to build, O(1) per query
  • Space — O(m · n)

Pitfalls

  • The extra zero row and column remove every special case for row1 = 0 or col1 = 0.
  • Forgetting to add back P[r1][c1] subtracts the top-left block twice.
  • Prefix sums reach at most 4 · 10^8 in absolute value under the constraints, so 32-bit integers suffice.

Reference solution

Python

from typing import List

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.p = [[0] * (n + 1) for _ in range(m + 1)]
        for r in range(m):
            for c in range(n):
                self.p[r + 1][c + 1] = matrix[r][c] + self.p[r][c + 1] + self.p[r + 1][c] - self.p[r][c]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        p = self.p
        return p[row2 + 1][col2 + 1] - p[row1][col2 + 1] - p[row2 + 1][col1] + p[row1][col1]

Java

class NumMatrix {
    private int[][] p;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        p = new int[m + 1][n + 1];
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                p[r + 1][c + 1] = matrix[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c];
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return p[row2 + 1][col2 + 1] - p[row1][col2 + 1] - p[row2 + 1][col1] + p[row1][col1];
    }
}

C++

class NumMatrix {
    vector<vector<int>> p;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        p.assign(m + 1, vector<int>(n + 1, 0));
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                p[r + 1][c + 1] = matrix[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c];
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return p[row2 + 1][col2 + 1] - p[row1][col2 + 1] - p[row2 + 1][col1] + p[row1][col1];
    }
};

JavaScript

var NumMatrix = function(matrix) {
    var m = matrix.length, n = matrix[0].length;
    this.p = [];
    for (var r = 0; r <= m; r++) {
        this.p.push([]);
        for (var c = 0; c <= n; c++) this.p[r].push(0);
    }
    for (var r2 = 0; r2 < m; r2++)
        for (var c2 = 0; c2 < n; c2++)
            this.p[r2 + 1][c2 + 1] = matrix[r2][c2] + this.p[r2][c2 + 1] + this.p[r2 + 1][c2] - this.p[r2][c2];
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    var p = this.p;
    return p[row2 + 1][col2 + 1] - p[row1][col2 + 1] - p[row2 + 1][col1] + p[row1][col1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal