LeetCode 304: Range Sum Query 2D - Immutable Solution

Master LeetCode problem 304 (Range Sum Query 2D - Immutable), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

304. Range Sum Query 2D - Immutable

Medium

Array Design Matrix Prefix Sum

Problem Explanation

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.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 304 (Range Sum Query 2D - Immutable)?

This page provides optimized solutions for LeetCode problem 304 (Range Sum Query 2D - Immutable) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 304 (Range Sum Query 2D - Immutable)?

The time complexity for LeetCode 304 (Range Sum Query 2D - Immutable) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 304 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 304 in Java, C++, or Python.

Back to LeetCode Solutions