algoadvance

Leetcode 304. Range Sum Query 2D

Problem Statement

The problem involves implementing a 2D range sum query. You are given a 2D matrix of integers, and you need to be able to calculate the sum of elements within a given rectangular area in the matrix efficiently. The operations that you need to support are:

• Initializing the class with the given matrix.
• Supporting the method sumRegion(row1, col1, row2, col2) which calculates the sum of the elements within the rectangle defined by its upper-left corner (row1, col1) and lower-right corner (row2, col2).

Clarifying Questions

1. Input Dimensions and Constraints:
   • What is the size of the matrix? (Typical constraints in real-world scenarios help to tailor optimizations.)
2. Initialization and Call Frequency:
   • How frequently is the matrix initialized compared to how often sumRegion is called? (Optimizations can focus on initialization vs querying time depending on the frequency.)
3. Matrix Characteristics:
   • Is the matrix mutable (i.e., the values of the matrix can change after initialization)? (Informs whether we need to handle mutable state or not.)

Assuming based on the problem name “Immutable” that the matrix does not change after being initialized.

Strategy

To ensure efficient querying, we can use a pre-processing step to construct a 2D prefix sum array that will allow us to compute the sum of any submatrix in constant time.

The prefix sum at any cell (i, j) in this array will represent the sum of all elements in the submatrix from (0,0) to (i, j) in the original matrix.

Steps

1. Preprocess Step: Construct a prefix sum matrix.
2. Query Step: Use the prefix sum matrix to return the sum for any given submatrix in constant time.

Code

class NumMatrix {
    private int[][] prefixSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        prefixSum = new int[m + 1][n + 1];
        
        // Building the prefix sum array
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // Include the current element and subtract the overlap
                prefixSum[i][j] = matrix[i - 1][j - 1] +
                                  prefixSum[i - 1][j] +
                                  prefixSum[i][j - 1] -
                                  prefixSum[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        // Use the precomputed sums to calculate the desired submatrix sum
        return prefixSum[row2 + 1][col2 + 1] -
               prefixSum[row2 + 1][col1] -
               prefixSum[row1][col2 + 1] +
               prefixSum[row1][col1];
    }
}

Time Complexity

• Initialization (Preprocessing): O(m * n) where m is the number of rows and n is the number of columns in the matrix. This is because we process each cell exactly once to compute the prefix sums.
• Query (sumRegion): O(1) for each query since the sum is calculated using a constant number of array lookups and arithmetic operations.

Example Usage

public class Main {
    public static void main(String[] args) {
        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 result = obj.sumRegion(2, 1, 4, 3);
        System.out.println(result); // Output should be 8
    }
}

This approach efficiently preprocesses the matrix to handle multiple range sum queries in constant time using the precomputed prefix sum matrix.

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?