Range Sum Query 2D - Immutable solution and explanation
Google
9 more videos on this problem
Range Sum Query 2D - Immutable - Leetcode 304 - PythonNeetCode · 13:17 · 82K views
花花酱 LeetCode 304. Range Sum Query 2D - Immutable - 刷题找工作 EP63Hua Hua · 10:18 · 16K views
Range Sum Query 2D | Leetcode #304Techdose · 15:39 · 15K views
Range Sum Query 2D - Immutable | Live Coding with Explanation | Leetcode - 304Algorithms Made Easy · 7:31 · 10K views
304. Range Sum Query 2D - Immutable | LEETCODE MEDIUM | PREFIX SUMcode Explainer · 12:28 · 2K views
Leetcode - Range Sum Query 2D - Immutable (Python)Timothy H Chang · 10:55 · 1K views
Range Sum Query 2D - Immutable | Prefix Sum on Matrix | Dp | 304 LeetCode | Day 12CodeWithSunny · 17:37 · 1K views
Range Sum Query 2D - Immutable | LeetCode 304 | Coders CampCoders Camp · 13:45 · 450 views
LeetCode 304. Range Sum Query 2D - Immutable | JSer - JavaScript & AlgorithmJSer · 22:17 · 446 views
Daily Leetcode #407: May 12, 2021 - 304. Range Sum Query 2D - ImmutableProgramming Live with Larry · 19:30 · 212 views
The problem
Given a 2D matrix matrix, handle multiple queries of the following type:
- Calculate the sum of the elements of
matrixinside 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 matrixmatrix.int sumRegion(int row1, int col1, int row2, int col2)Returns the sum of the elements ofmatrixinside the rectangle defined by its upper left corner(row1, col1)and lower right corner(row2, col2).
You must design an algorithm where sumRegion works on O(1) time complexity.
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 NumMatrix numMatrix = new NumMatrix([[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]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-104 <= matrix[i][j] <= 1040 <= row1 <= row2 < m0 <= col1 <= col2 < n- At most
104calls will be made tosumRegion.
Approach overview
Problem Overview: You receive a 2D matrix and must repeatedly return the sum of elements inside a rectangular region defined by (row1, col1) and (row2, col2). The matrix never changes, but the number of queries can be large. A naive sum per query is too slow, so the goal is to preprocess the matrix so each query runs in constant time.
Approach 1: Using 2D Prefix Sum (Preprocessing O(m*n), Query O(1))
This approach builds a cumulative sum matrix where each cell stores the total of all elements from the top-left corner to that position. During preprocessing, iterate through the matrix and compute prefix[i][j] using values from the top, left, and top-left diagonal. Once built, any submatrix sum can be computed using the inclusion–exclusion principle: subtract the extra regions above and left, then add back the overlapping corner. Query computation becomes a few constant-time arithmetic operations. Time complexity is O(m*n) to build the prefix matrix and O(1) per query, with O(m*n) extra space. This technique is a standard extension of prefix sum applied to a matrix and works well when the matrix is immutable and queries are frequent.
Approach 2: 2D Fenwick Tree (Binary Indexed Tree) (Update O(log m * log n), Query O(log m * log n))
A 2D Fenwick Tree stores partial sums in a structured tree-like array that supports efficient region queries. Each update propagates through index ranges using bit manipulation, and prefix sums are computed by traversing parent nodes. A rectangular sum query is derived by combining four prefix queries, similar to the prefix-sum inclusion–exclusion formula. Query and update operations both run in O(log m * log n) time with O(m*n) space. Even though the original problem is immutable, this structure becomes valuable if the matrix supports updates. It relies on concepts from array indexing and tree-based cumulative structures.
Recommended for interviews: The expected solution is the 2D Prefix Sum approach. Interviewers want to see that you recognize repeated range queries and convert them into a preprocessing problem. Building the prefix matrix shows understanding of cumulative sums and inclusion–exclusion logic. Mentioning a 2D Fenwick Tree demonstrates deeper knowledge of data structures for mutable range queries, but implementing it is usually unnecessary unless updates are part of the problem.
Approach 1: Approach 1: Using 2D Prefix Sum
This approach involves preprocessing the matrix to build a prefix sum array. The prefix sum at any index (i, j) in this array contains the sum of elements from (0, 0) to (i, j). With this preprocessed information, calculating any submatrix sum becomes feasible in constant time using the inclusion-exclusion principle.
For a query with corners (row1, col1) and (row2, col2), compute the sum using:
- Sum of elements from (0,0) to (row2,col2)
- Subtract areas that are not part of the required rectangle
- Adjust with intersections if need be
class NumMatrix:
def __init__(self, matrix):
if not matrix or not matrix[0]:
return
m, n = len(matrix), len(matrix[0])
self.sum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
self.sum[i][j] = matrix[i - 1][j - 1] + self.sum[i - 1][j] + self.sum[i][j - 1] - self.sum[i - 1][j - 1]
def sumRegion(self, row1, col1, row2, col2):
return self.sum[row2 + 1][col2 + 1] - self.sum[row2 + 1][col1] - self.sum[row1][col2 + 1] + self.sum[row1][col1]class NumMatrix {
private int[][] sum;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
sum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
}
}#include <vector>
using namespace std;
class NumMatrix {
public:
vector<vector<int>> sum;
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
sum.assign(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
}
};class NumMatrix {
constructor(matrix) {
const m = matrix.length;
const n = matrix[0].length;
this.sum = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
this.sum[i][j] = matrix[i - 1][j - 1] + this.sum[i - 1][j] + this.sum[i][j - 1] - this.sum[i - 1][j - 1];
}
}
}
sumRegion(row1, col1, row2, col2) {
return this.sum[row2 + 1][col2 + 1] - this.sum[row2 + 1][col1] - this.sum[row1][col2 + 1] + this.sum[row1][col1];
}
}#include <stdlib.h>
typedef struct {
int** sum;
int nrows;
int ncols;
} NumMatrix;
NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
NumMatrix* obj = (NumMatrix*) malloc(sizeof(NumMatrix));
obj->nrows = matrixSize;
obj->ncols = matrixColSize[0];
obj->sum = (int**) malloc((obj->nrows + 1) * sizeof(int*));
for(int i = 0; i <= obj->nrows; i++) {
obj->sum[i] = (int*) malloc((obj->ncols + 1) * sizeof(int));
for(int j = 0; j <= obj->ncols; j++) {
obj->sum[i][j] = 0;
}
}
for(int i = 1; i <= obj->nrows; i++) {
for(int j = 1; j <= obj->ncols; j++) {
obj->sum[i][j] = matrix[i-1][j-1] + obj->sum[i-1][j] + obj->sum[i][j-1] - obj->sum[i-1][j-1];
}
}
return obj;
}
int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
return obj->sum[row2+1][col2+1] - obj->sum[row2+1][col1] - obj->sum[row1][col2+1] + obj->sum[row1][col1];
}
void numMatrixFree(NumMatrix* obj) {
for(int i = 0; i <= obj->nrows; i++) {
free(obj->sum[i]);
}
free(obj->sum);
free(obj);
}public class NumMatrix {
private int[,] sum;
public NumMatrix(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
sum = new int[m + 1, n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i, j] = matrix[i - 1][j - 1] + sum[i - 1, j] + sum[i, j - 1] - sum[i - 1, j - 1];
}
}
}
public int SumRegion(int row1, int col1, int row2, int col2) {
return sum[row2 + 1, col2 + 1] - sum[row2 + 1, col1] - sum[row1, col2 + 1] + sum[row1, col1];
}
}The Python solution initializes and utilizes a prefix sum matrix to efficiently handle sumRegion queries.
Time Complexity: O(m * n) for precomputation, O(1) for result retrieval.
Space Complexity: O(m * n) for the prefix sum storage.
Approach 2: Approach 2: Using Fenwick Tree (Binary Indexed Tree) 2D
This approach involves using a 2D Fenwick Tree to update and query the matrix sums efficiently. Fenwick Trees provide a structure that allows for querying prefix sums, updating values, and hence facilitating the calculation of region sums after updates.
class NumMatrix {
private int[][] tree;
private int[][] nums;
private int m;
private int n;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return;
m = matrix.length;
n = matrix[0].length;
tree = new int[m + 1][n + 1];
nums = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
update(i, j, matrix[i][j]);
}
}
}
public void update(int row, int col, int val) {
int diff = val - nums[row][col];
nums[row][col] = val;
for (int i = row + 1; i <= m; i += i & -i) {
for (int j = col + 1; j <= n; j += j & -j) {
tree[i][j] += diff;
}
}
}
private int sum(int row, int col) {
int sum = 0;
for (int i = row + 1; i > 0; i -= i & -i) {
for (int j = col + 1; j > 0; j -= j & -j) {
sum += tree[i][j];
}
}
return sum;
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return sum(row2, col2) - sum(row2, col1 - 1) - sum(row1 - 1, col2) + sum(row1 - 1, col1 - 1);
}
}#include <vector>
using namespace std;
class NumMatrix {
public:
int m, n;
vector<vector<int>> tree;
vector<vector<int>> nums;
NumMatrix(vector<vector<int>>& matrix) {
m = matrix.size();
n = matrix[0].size();
tree.resize(m + 1, vector<int>(n + 1));
nums.resize(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
update(i, j, matrix[i][j]);
}
}
}
void update(int row, int col, int val) {
int diff = val - nums[row][col];
nums[row][col] = val;
for (int i = row + 1; i <= m; i += i & -i) {
for (int j = col + 1; j <= n; j += j & -j) {
tree[i][j] += diff;
}
}
}
int sumRange(int row1, int col1, int row2, int col2) {
return sum(row2, col2) - sum(row2, col1 - 1) - sum(row1 - 1, col2) + sum(row1 - 1, col1 - 1);
}
private:
int sum(int row, int col) {
int total = 0;
for (int i = row + 1; i > 0; i -= i & -i) {
for (int j = col + 1; j > 0; j -= j & -j) {
total += tree[i][j];
}
}
return total;
}
};The Java implementation adopts a similar logic to the C++ solution, using a 2D Fenwick Tree to support dynamic updates and range sum queries.
Time Complexity: O(log m * log n) per update or query.
Space Complexity: O(m * n) for the tree data structure.
Approach 3: Two-dimensional Prefix Sum
We use s[i + 1][j + 1] to represent the sum of all elements in the upper left part of the ith row and jth column, where indices i and j both start from 0. We can get the following prefix sum formula:
$
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + nums[i][j]
Then, the sum of the elements of the rectangle with (x_1, y_1) and (x_2, y_2) as the upper left corner and lower right corner respectively is:
s[x_2 + 1][y_2 + 1] - s[x_2 + 1][y_1] - s[x_1][y_2 + 1] + s[x_1][y_1]
In the initialization method, we preprocess the prefix sum array s, and in the query method, we directly return the result of the above formula.
The time complexity for initializing is O(m times n), and the time complexity for querying is O(1). The space complexity is O(m times n)$.
class NumMatrix {
private s: number[][];
constructor(matrix: number[][]) {
const m = matrix.length;
const n = matrix[0].length;
this.s = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
this.s[i + 1][j + 1] =
this.s[i + 1][j] + this.s[i][j + 1] - this.s[i][j] + matrix[i][j];
}
}
}
sumRegion(row1: number, col1: number, row2: number, col2: number): number {
return (
this.s[row2 + 1][col2 + 1] -
this.s[row2 + 1][col1] -
this.s[row1][col2 + 1] +
this.s[row1][col1]
);
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* var obj = new NumMatrix(matrix)
* var param_1 = obj.sumRegion(row1,col1,row2,col2)
*/type NumMatrix struct {
s [][]int
}
func Constructor(matrix [][]int) NumMatrix {
m, n := len(matrix), len(matrix[0])
s := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n+1)
}
for i, row := range matrix {
for j, v := range row {
s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + v
}
}
return NumMatrix{s}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
return this.s[row2+1][col2+1] - this.s[row2+1][col1] - this.s[row1][col2+1] + this.s[row1][col1]
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* param_1 := obj.SumRegion(row1,col1,row2,col2);
*/class NumMatrix(matrix: Array<IntArray>) {
private val n: Int
private val m: Int
private val matrix: Array<IntArray>
private val prefix_sums_matrix: Array<IntArray>
private var initialized: Boolean
init {
this.n = matrix.size
this.m = matrix[0].size
this.matrix = matrix
this.prefix_sums_matrix = Array(n + 1) { IntArray(m + 1) }
this.initialized = false
}
fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
this.init()
return this.prefix_sums_matrix[row2 + 1][col2 + 1] -
this.prefix_sums_matrix[row2 + 1][col1] -
this.prefix_sums_matrix[row1][col2 + 1] +
this.prefix_sums_matrix[row1][col1]
}
private fun init(): Boolean {
if (!this.initialized) {
for (i in 0..<this.n) {
for (j in 0..<this.m) {
this.prefix_sums_matrix[i + 1][j + 1] =
this.prefix_sums_matrix[i + 1][j] +
this.prefix_sums_matrix[i][j + 1] -
this.prefix_sums_matrix[i][j] +
this.matrix[i][j]
}
}
this.initialized = true
return true
}
return false
}
}
/**
* Your NumMatrix object will be instantiated and called as such: var obj = NumMatrix(matrix) var
* param_1 = obj.sumRegion(row1,col1,row2,col2)
*//**
* Your NumMatrix object will be instantiated and called as such:
* let obj = NumMatrix::new(matrix);
* let ret_1: i32 = obj.sum_region(row1, col1, row2, col2);
*/
struct NumMatrix {
// Of size (N + 1) * (M + 1)
prefix_vec: Vec<Vec<i32>>,
n: usize,
m: usize,
is_initialized: bool,
ref_vec: Vec<Vec<i32>>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl NumMatrix {
fn new(matrix: Vec<Vec<i32>>) -> Self {
NumMatrix {
prefix_vec: vec![vec![0; matrix[0].len() + 1]; matrix.len() + 1],
n: matrix.len(),
m: matrix[0].len(),
is_initialized: false,
ref_vec: matrix,
}
}
fn sum_region(&mut self, row1: i32, col1: i32, row2: i32, col2: i32) -> i32 {
if !self.is_initialized {
self.initialize_prefix_vec();
}
// Since i32 will let `rustc` complain, just make it happy
let row1: usize = row1 as usize;
let col1: usize = col1 as usize;
let row2: usize = row2 as usize;
let col2: usize = col2 as usize;
// Return the value in O(1)
self.prefix_vec[row2 + 1][col2 + 1]
- self.prefix_vec[row2 + 1][col1]
- self.prefix_vec[row1][col2 + 1]
+ self.prefix_vec[row1][col1]
}
fn initialize_prefix_vec(&mut self) {
// Initialize the prefix sum vector
for i in 0..self.n {
for j in 0..self.m {
self.prefix_vec[i + 1][j + 1] =
self.prefix_vec[i][j + 1] + self.prefix_vec[i + 1][j] - self.prefix_vec[i][j]
+ self.ref_vec[i][j];
}
}
self.is_initialized = true;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using 2D Prefix Sum | Time Complexity: O(m * n) for precomputation, O(1) for result retrieval. |
| Approach 2: Using Fenwick Tree (Binary Indexed Tree) 2D | Time Complexity: O(log m * log n) per update or query. |
| Two-dimensional Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| 2D Prefix Sum | Preprocess: O(m*n) Query: O(1) | O(m*n) | Best choice when the matrix is immutable and many range sum queries are expected |
| 2D Fenwick Tree (Binary Indexed Tree) | Update: O(log m * log n) Query: O(log m * log n) | O(m*n) | Useful when the matrix can change and you still need fast region sum queries |
Frequently asked questions
Is Range Sum Query 2D - Immutable easy or hard?
The problem is rated Medium because it requires recognizing the prefix sum pattern in two dimensions. Once the 2D cumulative formula is understood, the implementation is straightforward and commonly used in matrix query problems.
Range Sum Query 2D - Immutable Python/Java solution
Most implementations build a prefix matrix in the constructor and answer queries in a method like sumRegion(). The logic is identical across Python, Java, C++, JavaScript, and C#. Only syntax differs while the algorithm remains O(m*n) preprocessing and O(1) query time.
What is the best approach for Range Sum Query 2D - Immutable?
The optimal solution uses a 2D Prefix Sum matrix. Precompute cumulative sums for every cell so each query can be answered using inclusion–exclusion. This preprocessing takes O(m*n) time and space, while each range sum query runs in O(1).
Is Range Sum Query 2D - Immutable asked at Google/Amazon/Meta?
Range query problems with prefix sums appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include 1D range sums, mutable arrays, and matrix sum queries. Interviewers use these problems to test preprocessing strategies and space-time tradeoffs.
What data structure is used in Range Sum Query 2D - Immutable?
The main data structure is a 2D Prefix Sum array that stores cumulative sums for fast region queries. Advanced variants may use a 2D Fenwick Tree (Binary Indexed Tree) or Segment Tree when updates are allowed.
What is the time complexity of Range Sum Query 2D - Immutable?
Using the optimal 2D prefix sum technique, preprocessing the matrix takes O(m*n). After that, each submatrix sum query runs in constant O(1) time. Space complexity is also O(m*n) for the prefix matrix.
How to solve Range Sum Query 2D - Immutable in O(1) query time?
Precompute a 2D prefix sum array where each cell stores the sum of elements from (0,0) to (i,j). For a query rectangle, combine four prefix values using the inclusion–exclusion formula. This converts every query into a constant-time calculation.