Problem Description

You start with an n x n matrix filled with zeros. You're given a list of queries, where each query specifies a rectangular region in the matrix. For each query, you need to add 1 to every element within that rectangular region.

Each query is defined by four values: [row1, col1, row2, col2], where:

• (row1, col1) is the top-left corner of the rectangle
• (row2, col2) is the bottom-right corner of the rectangle

For each query, you add 1 to all elements mat[x][y] where row1 ≤ x ≤ row2 and col1 ≤ y ≤ col2.

After processing all queries, return the final matrix.

The solution uses a 2D difference array technique to efficiently handle range updates:

1. Marking boundaries: Instead of updating every element in each rectangular region (which would be inefficient), the solution marks the boundaries of each update region:

   • Add 1 at the top-left corner (x1, y1)
   • Subtract 1 at (x2+1, y1) to mark where the effect stops vertically
   • Subtract 1 at (x1, y2+1) to mark where the effect stops horizontally
   • Add 1 at (x2+1, y2+1) to correct the double subtraction

2. Prefix sum reconstruction: After marking all boundaries, the solution uses 2D prefix sums to reconstruct the final matrix:

   • For each cell, accumulate values from the cell above (mat[i-1][j])
   • Add values from the cell to the left (mat[i][j-1])
   • Subtract the diagonal overlap (mat[i-1][j-1]) to avoid double counting

This approach reduces the time complexity from O(queries × area) to O(n² + queries), making it much more efficient for multiple queries on large regions.

Intuition

The naive approach would be to iterate through each query and add 1 to every cell in the specified rectangle. However, this becomes inefficient when we have many queries or large rectangles, potentially resulting in O(queries × n²) time complexity.

The key insight is recognizing that we can defer the actual updates and instead mark only the boundaries of where changes begin and end. Think of it like turning on and off water taps - instead of manually filling every cup in a region, we can set up a system where water flows automatically to the right areas.

Consider what happens when we want to add 1 to a rectangle. If we think in 1D first: to add 1 to elements from index i to j, we can mark +1 at position i and -1 at position j+1. Then, when we compute the prefix sum, all elements between i and j will naturally get the +1 value.

Extending this to 2D, we need to mark four corners:

• +1 at (row1, col1): This starts the addition effect
• -1 at (row2+1, col1): This stops the effect from flowing beyond row2
• -1 at (row1, col2+1): This stops the effect from flowing beyond col2
• +1 at (row2+1, col2+1): This corrects for the double subtraction that would occur when both row and column boundaries overlap

The magic happens in the reconstruction phase. When we compute 2D prefix sums, each cell accumulates all the boundary markers that affect it. The formula mat[i][j] += mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1] essentially "spreads" the effects of all boundary markers across the matrix, automatically applying the correct increment to each cell based on which rectangles it belongs to.

This transforms our problem from "update many cells multiple times" to "mark a few boundaries once, then reconstruct the matrix once", dramatically improving efficiency.

Learn more about Prefix Sum patterns.

Solution Approach

The solution implements a 2D difference array technique combined with 2D prefix sum reconstruction. Here's how the implementation works:

Step 1: Initialize the Matrix

mat = [[0] * n for _ in range(n)]

Create an n × n matrix filled with zeros. This will serve as our difference array where we'll mark boundaries.

Step 2: Mark Boundaries for Each Query

for x1, y1, x2, y2 in queries:
    mat[x1][y1] += 1
    if x2 + 1 < n:
        mat[x2 + 1][y1] -= 1
    if y2 + 1 < n:
        mat[x1][y2 + 1] -= 1
    if x2 + 1 < n and y2 + 1 < n:
        mat[x2 + 1][y2 + 1] += 1

For each query defining a rectangle from (x1, y1) to (x2, y2):

• Add 1 at the top-left corner (x1, y1) to start the effect
• Subtract 1 at (x2+1, y1) if it's within bounds - this cancels the effect below row x2
• Subtract 1 at (x1, y2+1) if it's within bounds - this cancels the effect right of column y2
• Add 1 at (x2+1, y2+1) if it's within bounds - this corrects the double subtraction from the previous two operations

The boundary checks ensure we don't access indices outside the matrix.

Step 3: Reconstruct Using 2D Prefix Sums

for i in range(n):
    for j in range(n):
        if i:
            mat[i][j] += mat[i - 1][j]
        if j:
            mat[i][j] += mat[i][j - 1]
        if i and j:
            mat[i][j] -= mat[i - 1][j - 1]

This phase propagates the boundary markers throughout the matrix:

• mat[i][j] += mat[i-1][j]: Add the accumulated value from the cell above
• mat[i][j] += mat[i][j-1]: Add the accumulated value from the cell to the left
• mat[i][j] -= mat[i-1][j-1]: Subtract the diagonal cell to avoid double-counting (since it was included in both the above and left cells)

The conditions if i: and if j: check that we're not at the first row or column, preventing out-of-bounds access.

Time Complexity: O(n² + q) where q is the number of queries

• Marking boundaries: O(4q) = O(q)
• Reconstruction: O(n²)

Space Complexity: O(n²) for the matrix itself

This approach is significantly more efficient than the naive O(n² × q) solution when dealing with multiple queries or large rectangular regions.

Example Walkthrough

Let's walk through a concrete example with a 4×4 matrix and 2 queries:

• Query 1: [1, 1, 2, 2] - adds 1 to rectangle from (1,1) to (2,2)
• Query 2: [0, 0, 1, 1] - adds 1 to rectangle from (0,0) to (1,1)

Initial State:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Step 1: Process Query 1 [1, 1, 2, 2]

Mark boundaries:

• Add 1 at (1,1): the top-left corner
• Subtract 1 at (3,1): stops effect after row 2
• Subtract 1 at (1,3): stops effect after column 2
• Add 1 at (3,3): corrects double subtraction

0  0  0  0
0  1  0 -1
0  0  0  0
0 -1  0  1

Step 2: Process Query 2 [0, 0, 1, 1]

Mark boundaries on top of existing marks:

• Add 1 at (0,0): the top-left corner
• Subtract 1 at (2,0): stops effect after row 1
• Subtract 1 at (0,2): stops effect after column 1
• Add 1 at (2,2): corrects double subtraction

1  0 -1  0
0  1  0 -1
-1 0  1  0
0 -1  0  1

Step 3: Reconstruct with 2D Prefix Sums

Process row by row, left to right:

Row 0:

• (0,0): 1 (no cells above or left)
• (0,1): 1 + 0 = 1 (add left cell)
• (0,2): 1 + (-1) = 0 (add left cell)
• (0,3): 0 + 0 = 0 (add left cell)

After row 0: [1, 1, 0, 0]

Row 1:

• (1,0): 1 + 0 = 1 (add above cell)
• (1,1): 1 + 1 + 1 - 1 = 2 (above + left - diagonal)
• (1,2): 2 + 0 + 0 - 1 = 1 (above + left - diagonal)
• (1,3): 1 + (-1) + 0 - 0 = 0 (above + left - diagonal)

After row 1: [1, 2, 1, 0]

Row 2:

• (2,0): 1 + (-1) = 0
• (2,1): 2 + 0 + 0 - 1 = 1
• (2,2): 1 + 1 + 1 - 2 = 1
• (2,3): 0 + 0 + 1 - 1 = 0

After row 2: [0, 1, 1, 0]

Row 3:

• (3,0): 0 + 0 = 0
• (3,1): 1 + (-1) + 0 - 0 = 0
• (3,2): 1 + 0 + 0 - 1 = 0
• (3,3): 0 + 1 + 0 - 0 = 1

Final Result:

1 1 0 0
1 2 1 0
0 1 1 0
0 0 0 0

We can verify this is correct:

• Query 1 added 1 to cells (1,1), (1,2), (2,1), (2,2)
• Query 2 added 1 to cells (0,0), (0,1), (1,0), (1,1)
• Cell (1,1) was affected by both queries, so it has value 2
• All other affected cells have value 1

Solution Implementation

Time and Space Complexity

Time Complexity: O(q + n²) where q is the number of queries and n is the size of the matrix.

• The first loop iterates through all queries and performs constant time operations for each query: O(q)
• The second nested loop iterates through all n × n cells of the matrix to compute the prefix sum. Each cell performs constant time operations (at most 3 additions and 1 subtraction): O(n²)
• Total time complexity: O(q + n²)

Space Complexity: O(n²)

• The algorithm creates a 2D matrix mat of size n × n to store the difference array and final result: O(n²)
• No additional auxiliary space is used beyond the output matrix
• The space used for the input queries is not counted as it's part of the input
• Total space complexity: O(n²)

The algorithm uses a 2D difference array technique combined with 2D prefix sum computation to efficiently handle range updates. Instead of updating all cells in each query rectangle (which would be O(q × n²) in the worst case), it marks only the corners of each rectangle in O(1) time per query, then reconstructs the final values using prefix sums in a single pass.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Marking Coordinates

One of the most common mistakes is incorrectly placing the boundary markers, especially confusing which cells need +1 or -1. Many developers mistakenly place markers at:

• (x2, y1) instead of (x2+1, y1)
• (x1, y2) instead of (x1, y2+1)
• (x2, y2) instead of (x2+1, y2+1)

Why this happens: The intuition is that we want to mark the rectangle's boundaries, but the difference array technique requires marking positions outside the rectangle to stop the effect.

Solution: Remember that difference arrays mark where changes start and stop. The -1 markers must be placed one position beyond where you want the effect to end.

2. Missing Boundary Checks

Another frequent error is forgetting to check if x2+1 or y2+1 are within the matrix bounds before accessing those positions:

# WRONG - may cause IndexError
mat[x2 + 1][y1] -= 1  # What if x2 + 1 >= n?

# CORRECT
if x2 + 1 < n:
    mat[x2 + 1][y1] -= 1

Solution: Always verify that indices are within bounds before accessing array elements. When the boundary marker would be outside the matrix, it's safe to skip it since there's nothing beyond the matrix edge to affect.

3. Incorrect Order of Prefix Sum Operations

During reconstruction, applying the prefix sum operations in the wrong order or using wrong indices can lead to incorrect results:

# WRONG - using wrong indices
mat[i][j] += mat[i][j - 1]  # Should check j > 0 first
mat[i][j] += mat[i - 1][j]  # Should check i > 0 first

# WRONG - forgetting the subtraction
mat[i][j] += mat[i - 1][j]
mat[i][j] += mat[i][j - 1]
# Missing: mat[i][j] -= mat[i - 1][j - 1]

Solution: Follow the exact 2D prefix sum formula:

• Add from above (if not first row)
• Add from left (if not first column)
• Subtract diagonal overlap (if not first row AND not first column)

4. Attempting In-Place Updates During Iteration

Some might try to optimize by processing queries and computing prefix sums simultaneously, which leads to incorrect results:

# WRONG - mixing boundary marking with prefix sum computation
for query in queries:
    # Mark boundaries
    # Then immediately try to compute prefix sums
    # This doesn't work because all boundaries must be marked first

Solution: Keep the two phases separate:

1. First, mark ALL boundaries for ALL queries
2. Then, perform the 2D prefix sum reconstruction in a single pass

5. Off-by-One Errors in Loop Conditions

Using incorrect loop conditions during prefix sum reconstruction:

# WRONG - using >= instead of >
if i >= 1:  # This works but i > 0 is clearer
    mat[i][j] += mat[i - 1][j]

# WRONG - starting from 1 but not adjusting logic
for i in range(1, n):  # Starting from 1
    mat[i][j] += mat[i - 1][j]  # OK
    if i:  # This is always True since i starts from 1
        # Redundant check

Solution: Use clear, consistent conditions. Starting loops from 0 and using if i > 0: or if i: makes the logic more straightforward and prevents confusion.