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

LeetCode

https://leetcode.com/problems/range-sum-query-2d-immutable/description/

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.

Examples

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)

Different Approaches

1️⃣ Brute Force Approach (TLE)

🧠 Idea:

For each query, iterate through the submatrix and compute the sum.

💻 Code:

int sumRegion(int row1, int col1, int row2, int col2) {
    // Initialize sum to store the total sum of the submatrix
    int sum = 0;

    // Loop through each row from row1 to row2
    for (int i = row1; i <= row2; ++i) {
        // For the current row, loop through each column from col1 to col2
        for (int j = col1; j <= col2; ++j) {
            // Add the value at matrix[i][j] to the sum
            sum += matrix[i][j];
        }
    }

    // After summing all elements in the given region, return the result
    return sum;
}

Complexity Analysis:

• Time Complexity:O(row2 - row 1 + 1) * (col2 - col1 + 1)
• Space Complexity:O(1)

2️⃣ Row-wise Prefix Sum

🧠 Idea:

Store prefix sums for each row to speed up queries. You still iterate over rows, but reduce per-row work to O(1).

Code:

class NumMatrix {
    // 2D vector to store prefix sums of each row
    vector<vector<int>> rowPrefix;

public:
    // Constructor to initialize the prefix sum matrix
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();         // Number of rows
        int n = matrix[0].size();      // Number of columns

        // Copy original matrix to rowPrefix
        rowPrefix = matrix;

        // Calculate row-wise prefix sums
        for (int i = 0; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                // Add previous column value to current to make it cumulative
                rowPrefix[i][j] += rowPrefix[i][j - 1];
            }
        }
    }

    // Function to return the sum of elements inside the rectangle
    // defined by (row1, col1) as top-left and (row2, col2) as bottom-right
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;

        // Loop through each row from row1 to row2
        for (int i = row1; i <= row2; ++i) {
            // Use prefix sum to calculate the sum of columns from col1 to col2
            if (col1 == 0) {
                // If starting column is 0, just take prefix at col2
                sum += rowPrefix[i][col2];
            } else {
                // Else subtract prefix at col1 - 1 to get sum from col1 to col2
                sum += rowPrefix[i][col2] - rowPrefix[i][col1 - 1];
            }
        }

        return sum; // Return the total sum of the rectangle
    }
};

Complexity Analysis:

• Time Complexity:
  • Preprocessing: O(m * n)
  • Query: O(row2 - row 1 + 1)
• Space Complexity:O(m * n)

3️⃣ Prefix Sum (2D Preprocessing)

Code:

class NumMatrix {
    // 2D prefix sum matrix with extra row and column (1-based indexing)
    vector<vector<int>> prefix;

public:
    // Constructor to initialize the prefix sum matrix
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();          // Number of rows
        int n = matrix[0].size();       // Number of columns

        // Initialize prefix matrix with (m+1)x(n+1) size, all zeros
        // Extra row and column help avoid boundary checks later
        prefix = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

        // Build the prefix sum matrix
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // Compute sum of submatrix from (0,0) to (i,j)
                prefix[i + 1][j + 1] = matrix[i][j]
                                     + prefix[i][j + 1]   // Above
                                     + prefix[i + 1][j]   // Left
                                     - prefix[i][j];      // Remove overlap (diagonal)
            }
        }
    }

    // Function to return sum of submatrix from (row1,col1) to (row2,col2)
    int sumRegion(int row1, int col1, int row2, int col2) {
        // Apply inclusion-exclusion principle to get the region sum in O(1)
        return prefix[row2 + 1][col2 + 1]   // Total up to bottom-right
             - prefix[row2 + 1][col1]       // Remove left block
             - prefix[row1][col2 + 1]       // Remove top block
             + prefix[row1][col1];          // Add overlap back
    }
};

📊 Complexity Analysis:

• Time Complexity:
  • Preprocessing: O(m × n)
  • Time (query): O(1)
• Space Complexity:O(m × n)