algoadvance

You are given a 2D matrix matrix composed of only integers. 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 from the top-left element (row1, col1) to the bottom-right element (row2, col2) inclusive.

You must implement the NumMatrix class such that each call to sumRegion works in constant time (O(1)).

Example

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 = NumMatrix(matrix)
print(numMatrix.sumRegion(2, 1, 4, 3)) # Output: 8
print(numMatrix.sumRegion(1, 1, 2, 2)) # Output: 11
print(numMatrix.sumRegion(1, 2, 2, 4)) # Output: 12

Clarifying Questions

Before starting, let’s clarify a few points:

1. Matrix Constraints:
   • What are the size constraints for the matrix?
   • Are there any constraints on the values within the matrix?
2. Sum Queries:
   • Can we assume row1 <= row2 and col1 <= col2 for each query?

Assuming the problem constraints are standard for competitive programming problems, we will develop a plan to address the requirements.

Strategy

To ensure that each call to sumRegion works in constant time, we can use a prefix sum approach. The main steps are as follows:

1. Prefix Sum Calculation:
   • Create a prefix sum matrix where prefix[i][j] represents the sum of the matrix elements from (0,0) to (i-1,j-1).
2. Initialize Prefix Sum Matrix:
   • Compute prefix[i][j] such that it is the sum of all elements from the top-left corner (0,0) to (i-1,j-1).
3. Using Prefix Sum for Queries:
   • With the prefix sum matrix, calculate the sum of any submatrix using inclusion-exclusion principle: ```text sumRegion(row1, col1, row2, col2) = prefix[row2 + 1][col2 + 1]
     • prefix[row1][col2 + 1]
     • prefix[row2 + 1][col1]
     • prefix[row1][col1] ```

Code

class NumMatrix:
    def __init__(self, matrix):
        if not matrix or not matrix[0]:
            self.prefix_sum = []
            return

        rows, cols = len(matrix), len(matrix[0])
        self.prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
        
        for r in range(1, rows + 1):
            for c in range(1, cols + 1):
                self.prefix_sum[r][c] = matrix[r-1][c-1] + self.prefix_sum[r-1][c] + self.prefix_sum[r][c-1] - self.prefix_sum[r-1][c-1]

    def sumRegion(self, row1, col1, row2, col2):
        return (self.prefix_sum[row2 + 1][col2 + 1]
                - self.prefix_sum[row1][col2 + 1]
                - self.prefix_sum[row2 + 1][col1]
                + self.prefix_sum[row1][col1])

# Example Usage
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 = NumMatrix(matrix)
print(numMatrix.sumRegion(2, 1, 4, 3))  # Output: 8
print(numMatrix.sumRegion(1, 1, 2, 2))  # Output: 11
print(numMatrix.sumRegion(1, 2, 2, 4))  # Output: 12

Time Complexity

• Initialization (constructor): O(m * n), where m and n are the number of rows and columns respectively, for building the prefix sum matrix.
• Query (sumRegion): O(1), as it only involves a few lookups and arithmetic operations.

This ensures that our sumRegion function operates in constant time, meeting the problem’s requirement.

Try our interview co-pilot at AlgoAdvance.com

• 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?