Increment Submatrices by One

Increment Submatrices by One

What is this problem about?

In the Increment Submatrices by One coding problem, you are given an $n imes n$ matrix initially filled with zeros. You receive a series of queries, where each query provides the coordinates $(r1, c1)$ and $(r2, c2)$ of a submatrix. For each query, you must increment every cell in that submatrix by 1. After all queries are processed, return the final matrix.

Why is this asked in interviews?

Companies like Meta and Google ask this to test your knowledge of Prefix Sum interview patterns in 2D. A naive solution would iterate through every cell in the submatrix for every query, leading to $O(Q imes N^2)$ complexity. Interviewers expect an $O(Q + N^2)$ solution, which demonstrates your ability to use "Difference Arrays" to handle range updates efficiently.

Algorithmic pattern used

This problem uses the 2D Difference Array or 2D Prefix Sum pattern.

1. For each query $(r1, c1, r2, c2)$:
   • diff[r1][c1] += 1
   • diff[r1][c2+1] -= 1 (if within bounds)
   • diff[r2+1][c1] -= 1 (if within bounds)
   • diff[r2+1][c2+1] += 1 (if within bounds)
2. After processing all queries, calculate the 2D prefix sum of the diff array to get the final values for each cell. The prefix sum formula: res[i][j] = diff[i][j] + res[i-1][j] + res[i][j-1] - res[i-1][j-1].

Example explanation

$3 imes 3$ matrix, Query: (1,1) to (2,2).

1. Mark diff[1][1] = 1.
2. Mark diff[1][3] = -1 (Stop the row increment).
3. Mark diff[3][1] = -1 (Stop the column increment).
4. Mark diff[3][3] = 1 (Fix the double-subtraction at the corner).
5. Summing up: All cells from (1,1) to (2,2) will eventually accumulate the '+1' through the prefix sum calculation.

Common mistakes candidates make

• Naive Implementation: Writing four nested loops ($O(Q imes N^2)$), which will time out for large $N$ or $Q$.
• Boundary Errors: Forgetting to handle the $+1$ offset for the end coordinates in the difference array.
• Prefix Sum Logic: Incorrectly calculating the 2D prefix sum (forgetting to subtract the top-left overlapping area).

Interview preparation tip

Master the 1D difference array first (incrementing range $[L, R]$ in $O(1)$). The 2D version is just an extension of that principle. It is a vital technique for any competitive programming or "Hard" level algorithmic interview.