We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Increment Submatrices by One

Number: 2625

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an n x n 0-indexed matrix initially filled with zeros, we need to process a series of queries. Each query, defined by the coordinates [row1, col1, row2, col2], indicates that we should increment every element within the submatrix defined by the top-left corner (row1, col1) and the bottom-right corner (row2, col2) by one. Return the final state of the matrix after processing all queries.

Key Insights

  • Instead of updating each element within a query's submatrix (which could be costly), use a 2D difference array (prefix sum technique) for efficient range updates.
  • For each query, update only the borders in the difference matrix:
    • Add 1 at (row1, col1).
    • Subtract 1 at (row1, col2 + 1) if within bounds.
    • Subtract 1 at (row2 + 1, col1) if within bounds.
    • Add 1 at (row2 + 1, col2 + 1) if within bounds.
  • After processing all queries, convert the difference matrix into the final matrix using two-pass prefix sums (first row-wise then column-wise).

Space and Time Complexity

Time Complexity: O(q + n^2), where q is the number of queries.
Space Complexity: O(n^2) for the extra difference matrix used.

Solution

We use a 2D difference (or prefix sum) approach to handle the range updates efficiently. Instead of incrementing every element in a queried submatrix directly, we update only the corners of the submatrix in a difference matrix. After processing every query, we compute prefix sums to convert the difference matrix to the actual updated matrix.

Steps:

  1. Initialize a 2D difference matrix of size (n+1) x (n+1) with zeros.
  2. For each query [row1, col1, row2, col2]:
    • Add 1 at diff[row1][col1].
    • Subtract 1 at diff[row1][col2 + 1] if col2+1 < n.
    • Subtract 1 at diff[row2 + 1][col1] if row2+1 < n.
    • Add 1 at diff[row2 + 1][col2 + 1] if both row2+1 and col2+1 are < n.
  3. Compute the prefix sum row-wise and then column-wise to form the final matrix.
  4. Return the updated matrix up to n x n.

This approach allows each query to be processed in constant time and handles large inputs efficiently.

Code Solutions

# Python Solution
class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        # Initialize a difference matrix of size (n+1) x (n+1) with zeros.
        diff = [[0] * (n + 1) for _ in range(n + 1)]
        
        # Process each query to update the difference matrix.
        for row1, col1, row2, col2 in queries:
            diff[row1][col1] += 1  # Increment top-left corner.
            if col2 + 1 < n:
                diff[row1][col2 + 1] -= 1  # Subtract right to the submatrix.
            if row2 + 1 < n:
                diff[row2 + 1][col1] -= 1  # Subtract below the submatrix.
            if row2 + 1 < n and col2 + 1 < n:
                diff[row2 + 1][col2 + 1] += 1  # Correct double subtraction.
        
        # Build the final matrix from the difference matrix using prefix sum.
        # First, process prefix sums row-wise.
        for i in range(n):
            for j in range(1, n):
                diff[i][j] += diff[i][j-1]
        
        # Then, process prefix sums column-wise.
        for j in range(n):
            for i in range(1, n):
                diff[i][j] += diff[i-1][j]
        
        # Extract the first n x n matrix as result.
        return [row[:n] for row in diff[:n]]
← Back to All Questions