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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Increment Submatrices by One

Difficulty: Medium

Problem Description

You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes. You are also given a 2D integer array query. For each query[i] = [row1i, col1i, row2i, col2i], you should do the following operation: Add 1 to every element in the submatrix with the top left corner (row1i, col1i) and the bottom right corner (row2i, col2i). Return the matrix mat after performing every query.

Key Insights

  • The problem involves updating submatrices in a 2D matrix based on given queries.
  • Directly iterating through the submatrix for each query could lead to inefficiency, especially for large matrices and many queries.
  • A more efficient approach involves using a difference array or a prefix sum technique to handle multiple updates efficiently.

Space and Time Complexity

Time Complexity: O(n^2 + q), where n is the dimension of the matrix and q is the number of queries. The O(n^2) accounts for constructing the result matrix and O(q) for processing the queries. Space Complexity: O(n^2) for the result matrix.

Solution

To efficiently update the matrix, we can use a difference array technique. We will create an auxiliary matrix to mark the increments at the corners of the submatrices defined by the queries. After processing all queries, we will compute the final matrix by taking cumulative sums based on the auxiliary matrix. This method allows us to perform multiple updates in constant time for each query.

Code Solutions

def incrementSubmatrices(n, queries):
    # Initialize the result matrix with zeroes
    mat = [[0] * n for _ in range(n)]
    
    # Process each query
    for row1, col1, row2, col2 in queries:
        mat[row1][col1] += 1  # Top-left corner
        if row2 + 1 < n:      # Bottom-left corner
            mat[row2 + 1][col1] -= 1
        if col2 + 1 < n:      # Top-right corner
            mat[row1][col2 + 1] -= 1
        if row2 + 1 < n and col2 + 1 < n:  # Bottom-right corner
            mat[row2 + 1][col2 + 1] += 1
    
    # Apply prefix sums to get the final matrix
    for i in range(n):
        for j in range(n):
            if i > 0:
                mat[i][j] += mat[i - 1][j]
            if j > 0:
                mat[i][j] += mat[i][j - 1]
            if i > 0 and j > 0:
                mat[i][j] -= mat[i - 1][j - 1]
    
    return mat
← Back to All Questions