Range Sum Query 2D - Mutable

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Range Sum Query 2D - Mutable

Given a 2D matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). The matrix is mutable, meaning its values can be updated.

Requirement

NumMatrix(matrix): Initializes the data structure.
update(row, col, val): Updates the value at (row, col) to val.
sumRegion(row1, col1, row2, col2): Returns the sum of elements within the specified rectangle.

Hard

Examples

Input: NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5]]), sumRegion(2,1,4,3), update(3,2,2), sumRegion(2,1,4,3)
Output: 8, 6

Approach 1

Level I: Row-wise Prefix Sums

Intuition

For each row, maintain a 1D prefix sum array. For sumRegion, iterate through each row in the range $[r1, r2]$ and compute the sum of that row's segment in $O(1)$ using the prefix sums. This makes update $O(N)$ and query $O(M)$ .

⏱ Update: O(N), Query: O(M).💾 O(M * N).

Detailed Dry Run

Matrix: [[1, 2], [3, 4]]. Row1 Prefix: [1, 3]. Row2 Prefix: [3, 7]. SumRegion(0,0,1,1) = (3-0) + (7-0) = 10.

java

class NumMatrix {
    int[][] rowPrefix; int[][] mat;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        mat = matrix; rowPrefix = new int[m][n + 1];
        for(int i=0; i<m; i++) for(int j=0; j<n; j++) rowPrefix[i][j+1] = rowPrefix[i][j] + matrix[i][j];
    }
    public void update(int r, int c, int val) {
        int delta = val - mat[r][c]; mat[r][c] = val;
        for(int j=c+1; j<rowPrefix[r].length; j++) rowPrefix[r][j] += delta;
    }
    public int sumRegion(int r1, int c1, int r2, int c2) {
        int sum = 0; for(int i=r1; i<=r2; i++) sum += rowPrefix[i][c2+1] - rowPrefix[i][c1];
        return sum;
    }
}

Approach 2

Level II: 2D Binary Indexed Tree (BIT)

Intuition

Extend the 1D BIT to 2D. Each node $(i, j)$ in the BIT stores a prefix sum. update and query both take $O(log M * log N)$ time.

⏱ Update: O(log M * log N), Query: O(log M * log N).💾 O(M * N).

java

class NumMatrix {
    int[][] tree, nums; int m, n;
    public NumMatrix(int[][] matrix) {
        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 delta = 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] += delta;
    }
    public int sumRegion(int r1, int c1, int r2, int c2) {
        return query(r2 + 1, c2 + 1) - query(r1, c2 + 1) - query(r2 + 1, c1) + query(r1, c1);
    }
    private int query(int row, int col) {
        int sum = 0;
        for (int i = row; i > 0; i -= i & -i)
            for (int j = col; j > 0; j -= j & -j) sum += tree[i][j];
        return sum;
    }
}

Approach 3

Level III: 2D Segment Tree (Quadtree based)

Intuition

Build a segment tree where each node represents a rectangular region. update and query take $O(log M * log N)$ . Generally more powerful but harder to implement than BIT.

⏱ Update: O(log M * log N), Query: O(log M * log N).💾 O(M * N).

java

/* 2D Segment Tree code placeholder */

← Previous QuestionData Stream as Disjoint Intervals

Next Question →Snapshot Array

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.