Range Sum Query 2D - Immutable

LeetCode 304 | Difficulty: Medium

Medium

Problem Description

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 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.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 will be made to `sumRegion`.

Topics: Array, Design, Matrix, Prefix Sum

---

Approach

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 156 ms)

Metric	Value
Runtime	156 ms
Memory	35.4 MB
Date	2020-02-10

Solution

public class NumMatrix {

    int[,] dp;
    int m ;
    int n;
    public NumMatrix(int[][] matrix)
    {
        this.m = matrix.GetLength(0);
        this.n = m>0 ? matrix[0].GetLength(0) : 0;
        dp = new int[m+1,n+1];
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i,j] = dp[i-1,j]+ dp[i,j-1] + matrix[i-1][j-1] - dp[i-1,j-1];
            }
        }
        
        
    }

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

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.SumRegion(row1,col1,row2,col2);
 */

---

Complexity Analysis

Approach	Time	Space
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify the expected time complexity for each operation before choosing data structures.