#2536

Medium

LeetCode Problem Workspace

Increment Submatrices by One

Increment Submatrices by One focuses on efficiently updating submatrices using row-wise prefix sums in an n by n matrix.

array matrix prefix sum

Problem Statement

You are given an integer n and an n x n matrix filled with zeros. Each query specifies a rectangular submatrix defined by top-left and bottom-right coordinates.

For each query [row1, col1, row2, col2], increment every element inside the specified submatrix by one. Return the final matrix after applying all queries, ensuring efficient handling for large n.

Examples

Example 1

Input: n = 3, queries = [[1,1,2,2],[0,0,1,1]]

Output: [[1,1,0],[1,2,1],[0,1,1]]

The diagram above shows the initial matrix, the matrix after the first query, and the matrix after the second query.

In the first query, we add 1 to every element in the submatrix with the top left corner (1, 1) and bottom right corner (2, 2).
In the second query, we add 1 to every element in the submatrix with the top left corner (0, 0) and bottom right corner (1, 1).

Example 2

Input: n = 2, queries = [[0,0,1,1]]

Output: [[1,1],[1,1]]

The diagram above shows the initial matrix and the matrix after the first query.

In the first query we add 1 to every element in the matrix.

Constraints

1 <= n <= 500
1 <= queries.length <= 104
0 <= row1i <= row2i < n
0 <= col1i <= col2i < n

Solution Approach

Naive iteration per query

Loop through each query and increment every element in the submatrix individually. This is simple but inefficient for large matrices or many queries.

Row-wise prefix sum optimization

Treat each row as a separate array. For each query, increment the start column and decrement the column after the end, then apply prefix sums per row. This reduces per-query work from O(n^2) to O(n), aligning with the Array plus Matrix pattern.

Final matrix reconstruction

After processing all queries with row-wise differences, accumulate prefix sums along each row to get the final values. This avoids redundant updates and handles multiple overlapping queries efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * q) using the row-wise prefix sum method, where q is the number of queries, compared to O(q * n^2) for naive updates. Space complexity is O(n^2) for the matrix plus O(n) extra for row differences.

What Interviewers Usually Probe

Asks about handling multiple overlapping submatrices efficiently.
Mentions optimizing from naive element-wise updates to prefix sum techniques.
Checks understanding of Array plus Matrix patterns and row-level operations.

Common Pitfalls or Variants

Common pitfalls

Trying to increment all elements directly for each query, causing TLE for large n.
Forgetting to apply prefix sums after row-wise difference updates.
Confusing row and column indices when applying submatrix increments.

Follow-up variants

Increment submatrices with arbitrary values instead of one.
Apply similar updates on non-square matrices or rectangular grids.
Count how many times each cell exceeds a threshold after multiple queries.

FAQ

What is the main pattern behind Increment Submatrices by One?

The pattern is Array plus Matrix, where each row can be treated as a 1D array to apply prefix sums for efficient submatrix increments.

Can I use naive iteration for all queries?

Naive iteration works for small n but will timeout for large n due to O(q * n^2) complexity.

How do prefix sums improve performance in this problem?

They let you update row segments efficiently, reducing repeated element-wise increments and handling overlapping queries quickly.

Does this method work for non-square matrices?

Yes, the row-wise prefix sum approach can be applied to rectangular matrices as long as you track row differences correctly.

What is a common error when applying row-wise differences?

Forgetting to decrement the column after the end index of the submatrix in each row, which results in incorrect final values.

terminal

Solution

Solution 1: 2D Difference Array

A 2D difference array is a technique used to efficiently handle range updates on 2D arrays. We can implement fast updates on submatrices by maintaining a difference matrix of the same size as the original matrix.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]
        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 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]
        return mat

Continue Practicing

#2428 maximum sum of an hourglass #2245 maximum trailing zeros in a cornered path #2906 construct product matrix