Increment Submatrices by One - Video Solutions

Problem Overview: You are given an n x n matrix initially filled with zeros and a list of queries. Each query defines a submatrix using coordinates [r1, c1, r2, c2]. Every cell inside that rectangle must be incremented by one. After processing all queries, return the final matrix.

Approach 1: Naive Simulation (Time: O(q * n^2), Space: O(1) extra)

The most direct solution simulates each query exactly as described. For every query, iterate through rows from r1 to r2 and columns from c1 to c2, incrementing each cell by one. The implementation is straightforward and useful when constraints are small. However, if the matrix is large or the number of queries grows, this becomes expensive because each query may touch up to n^2 cells.

This approach works as a baseline to confirm correctness but does not scale well. In worst cases with thousands of queries and large matrices, repeated updates dominate runtime.

Approach 2: 2D Difference Array + Prefix Sum (Time: O(n^2 + q), Space: O(n^2))

The optimal approach avoids updating every cell of a submatrix individually. Instead, treat each update as a boundary operation using a 2D difference array. For a query [r1, c1, r2, c2], apply four corner updates:

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

These operations mark where increments start and stop. After processing all queries, compute a 2D prefix sum over the matrix to propagate the increments to every affected cell. Each cell accumulates contributions from previous rows and columns, producing the final grid.

This technique is a classic extension of the difference-array idea commonly used in array problems. The prefix propagation step relies on concepts from prefix sum computation applied over a matrix. Instead of repeatedly modifying large regions, you convert each query into constant-time boundary updates.

The result is a major improvement: queries cost O(1) each, and the final reconstruction costs O(n^2). This makes the approach efficient even when the query list is large.

Recommended for interviews: Interviewers expect the prefix sum optimization. Implementing the naive simulation first shows you understand the problem mechanics. Recognizing that repeated region updates can be replaced with a difference array demonstrates deeper algorithmic thinking and familiarity with range-update techniques.