Increment Submatrices by One

main.md

Question

Approach

I use a 2D difference array (Imos) to apply each submatrix +1 in O(1) time per query, then recover the final matrix with 2D prefix sums. Concretely, I maintain an (n+1)×(n+1) diff array and for each query (r1,c1,r2,c2) I do:

• diff[r1][c1] += 1
• diff[r1][c2+1] -= 1
• diff[r2+1][c1] -= 1
• diff[r2+1][c2+1] += 1

After processing all queries I compute prefix sums over rows then columns (or vice-versa) and read the top-left n×n part as the answer.

Implementation

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        diff = [[0] * (n + 1) for _ in range(n + 1)]
        
        for r1, c1, r2, c2 in queries:
            diff[r1][c1] += 1
            diff[r1][c2 + 1] -= 1
            diff[r2 + 1][c1] -= 1
            diff[r2 + 1][c2 + 1] += 1
        
        for i in range(n):
            row_acc = 0
            for j in range(n):
                row_acc += diff[i][j]
                diff[i][j] = row_acc
        
        for j in range(n):
            col_acc = 0
            for i in range(n):
                col_acc += diff[i][j]
                diff[i][j] = col_acc
        
        return [diff[i][:n] for i in range(n)]

Complexities

• Time: O(n² + q)
• Space: O(n²)

That's cool