algoadvance

Leetcode 304. Range Sum Query 2D

Problem Statement

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(vector<vector<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).

Notes:

• You must provide a solution where sumRegion is called multiple times.
• The given matrix size will be between 1x1 and 200x200.

Example:

    vector<vector<int>> 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}
    };

    NumMatrix *obj = new NumMatrix(matrix);
    int param_1 = obj->sumRegion(2, 1, 4, 3); // Output: 8
    int param_2 = obj->sumRegion(1, 1, 2, 2); // Output: 11
    int param_3 = obj->sumRegion(1, 2, 2, 4); // Output: 12

Clarifying Questions:

1. Should we handle matrices that contain only zero values?
   • Yes, the approach should be generalized.
2. Are all the coordinates for calling sumRegion within the bounds of the matrix?
   • Yes, you can assume the coordinates will be valid.

Strategy:

To make the sumRegion calls efficient, precompute the sum of all submatrices from (0,0) to (i,j), storing these sums in a 2D prefix sum array. The sum of any submatrix (row1, col1) to (row2, col2) can be computed in constant time using this prefix sum array.

The prefix sum dp[i][j] represents the sum of elements from the top-left corner (0,0) to (i,j). The computation follows: [ \text{dp}[i][j] = \text{matrix}[i][j] + \text{dp}[i-1][j] + \text{dp}[i][j-1] - \text{dp}[i-1][j-1] ]

Code:

class NumMatrix {
private:
    vector<vector<int>> dp;
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        dp.resize(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = matrix[i-1][j-1] 
                           + dp[i-1][j] 
                           + dp[i][j-1] 
                           - dp[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] 
             - dp[row1][col2 + 1] 
             - dp[row2 + 1][col1] 
             + dp[row1][col1];
    }
};

Time Complexity:

• Preprocessing Time: (O(m \times n)), where (m) is the number of rows and (n) is the number of columns.
• Query Time: (O(1)) per query due to the computed prefix sum array.

This approach ensures that the sumRegion queries are efficient regardless of the matrix size, thereby providing optimal performance for multiple queries.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?