304. Range Sum Query 2D - Immutable

Explanation

To achieve O(1) time complexity for the sumRegion operation, we can precompute the sum of all elements from (0, 0) to each cell (i, j) in the matrix. By doing this, we can calculate the sum of any rectangle by using the precomputed sums.

Let's define a 2D array dp where dp[i][j] stores the sum of all elements from (0, 0) to (i, j) in the matrix. The sum of a rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2) can be calculated as dp[row2][col2] - dp[row1-1][col2] - dp[row2][col1-1] + dp[row1-1][col1-1].

The above formula includes the sum of the rectangle from (0, 0) to (row2, col2) and subtracts the extra sums from the top and left rectangles, while adding the overlapping sum once to avoid double subtraction.

Time Complexity:

Initializing the dp array takes O(m*n) time.
Calculating the sum of a rectangle takes O(1) time.
Overall, the time complexity is O(m*n) for initialization and O(1) for each query.

Space Complexity: O(m*n) for storing the precomputed sums.

View Leetcode Problem

class NumMatrix {
    int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m][n];

        dp[0][0] = matrix[0][0];

        // Fill the first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
        }

        // Fill the first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }

        // Fill rest of dp array
        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] - dp[i - 1][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (dp == null) {
            return 0;
        }

        int top = row1 == 0 ? 0 : dp[row1 - 1][col2];
        int left = col1 == 0 ? 0 : dp[row2][col1 - 1];
        int topLeft = (row1 == 0 || col1 == 0) ? 0 : dp[row1 - 1][col1 - 1];

        return dp[row2][col2] - top - left + topLeft;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation

Code Editor (Testing phase)

Improve Your Solution