# Increment Submatrices by One
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/increment-submatrices-by-one)
Canonical: https://scaleengineer.com/dsa/problems/increment-submatrices-by-one
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
---
## Problem
You are given a positive integer `n`, indicating that we initially have an `n x n` **0-indexed** integer matrix `mat` filled with zeroes.

You are also given a 2D integer array `query`. For each `query[i] = [row1i, col1i, row2i, col2i]`, you should do the following operation:

* Add `1` to **every element** in the submatrix with the **top left** corner `(row1i, col1i)` and the **bottom right** corner `(row2i, col2i)`. That is, add `1` to `mat[x][y]` for all `row1i <= x <= row2i` and `col1i <= y <= col2i`.

Return _the matrix_ `mat` _after performing every query._

**Example 1:**

![](https://assets.glich.co/dsa/increment-submatrices-by-one/image0.png) 

**Input:** n = 3, queries = [[1,1,2,2],[0,0,1,1]]
**Output:** [[1,1,0],[1,2,1],[0,1,1]]
**Explanation:** 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:**

![](https://assets.glich.co/dsa/increment-submatrices-by-one/image1.png) 

**Input:** n = 2, queries = [[0,0,1,1]]
**Output:** [[1,1],[1,1]]
**Explanation:** 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`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We initialize an `n x n` matrix with zeros. Then, for each query, we iterate over all the cells within the specified rectangular submatrix and increment their values by one.
**Time:** O(q * n^2) - Let `q` be the number of queries. For each query, in the worst case, we might have to update all `n*n` cells of the matrix (e.g., a query `[0, 0, n-1, n-1]`). This leads to a total time complexity proportional to the number of queries multiplied by the size of the matrix. · **Space:** O(n^2) - We need to store the `n x n` matrix.
**Pros:** Simple to understand and implement.; Correct for all valid inputs, assuming no time constraints.
**Cons:** Highly inefficient for large inputs, especially when the submatrices in queries are large.; Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits due to its high time complexity.
### Explanation
The brute-force method is the most intuitive way to solve the problem. It follows the problem statement literally.

1.  We start by creating the `n x n` matrix, `mat`, and filling it with zeros.
2.  We then loop through the `queries` array. Each element in this array is another array representing a single query: `[row1, col1, row2, col2]`.
3.  For each query, we use a pair of nested loops. The outer loop runs from `row1` to `row2`, and the inner loop runs from `col1` to `col2`. These loops cover every cell in the submatrix.
4.  In the body of the inner loop, we simply perform the operation `mat[i][j]++`.
5.  After the outer loop finishes processing all the queries, the `mat` will hold the final values, and we return it.

```java
class Solution {
    public int[][] rangeAddQueries(int n, int[][] queries) {
        int[][] mat = new int[n][n];
        
        for (int[] query : queries) {
            int row1 = query[0];
            int col1 = query[1];
            int row2 = query[2];
            int col2 = query[3];
            
            for (int i = row1; i <= row2; i++) {
                for (int j = col1; j <= col2; j++) {
                    mat[i][j]++;
                }
            }
        }
        
        return mat;
    }
}
```
### Algorithm
- Initialize an `n x n` matrix `mat` with all zeros.
- Iterate through each query `[row1, col1, row2, col2]` in the `queries` array.
- For each query, use nested loops to iterate through every cell `(i, j)` in the submatrix defined by the query, where `row1 <= i <= row2` and `col1 <= j <= col2`.
- Inside the inner loop, increment the value of `mat[i][j]` by 1.
- After iterating through all queries, return the final `mat`.

## 2D Difference Array (Prefix Sum)
This optimized approach uses a technique known as a 2D difference array (or 2D prefix sum). Instead of updating every cell in a submatrix for each query, we only mark the boundaries of the submatrix in an auxiliary matrix. A single `+1` operation on a submatrix can be represented by four updates on the corners of the region. After processing all queries in this manner, we can reconstruct the final matrix from the difference matrix in a single pass using prefix sum calculations.
**Time:** O(q + n^2) - Let `q` be the number of queries. Processing all queries takes O(q) time, as each query involves a constant number of operations (at most 4). Reconstructing the final matrix from the difference matrix takes O(n^2) time. The total complexity is dominated by the larger of these two terms. · **Space:** O(n^2) - We use an `n x n` matrix to store the differences and then the final result. No extra space beyond the result matrix is needed if done in-place.
**Pros:** Very efficient, especially for a large number of queries.; Reduces the complexity of processing queries from O(n^2) per query to O(1) per query.
**Cons:** The logic is more complex to understand compared to the brute-force approach.; It still requires O(n^2) space, which can be large for a very large `n`.
### Explanation
The key idea is to avoid redundant work. A single query affects a rectangular region. We can represent this update by making changes only at the corners of this region in a temporary 'difference' matrix.

1.  We initialize an `n x n` matrix, `mat`, with zeros. We will use this matrix to store the differences.
2.  For each query `[r1, c1, r2, c2]`, we apply four changes:
    -   `mat[r1][c1]++`: This marks the top-left corner. When we later compute prefix sums, this `+1` will propagate to all cells `(i, j)` where `i >= r1` and `j >= c1`.
    -   `mat[r1][c2 + 1]--` (if `c2 + 1 < n`): This cancels the effect of the `+1` for all cells in the same rows but to the right of the submatrix (`j > c2`).
    -   `mat[r2 + 1][c1]--` (if `r2 + 1 < n`): This cancels the effect for all cells in the same columns but below the submatrix (`i > r2`).
    -   `mat[r2 + 1][c2 + 1]++` (if both `r2 + 1 < n` and `c2 + 1 < n`): The previous two subtractions have double-cancelled the effect for the region `i > r2` and `j > c2`. We add `1` back to correct this.
3.  After all queries are processed, `mat` holds the difference information. We now need to convert it to the actual values by computing 2D prefix sums.
4.  First, we iterate through each row and compute its prefix sum: `for i from 0 to n-1, for j from 1 to n-1, mat[i][j] += mat[i][j-1]`.
5.  Next, we iterate through each column and compute its prefix sum: `for j from 0 to n-1, for i from 1 to n-1, mat[i][j] += mat[i-1][j]`.
6.  The resulting `mat` is the final answer.

```java
class Solution {
    public int[][] rangeAddQueries(int n, int[][] queries) {
        int[][] mat = new int[n][n];
        
        // Step 1: Apply all query operations on the difference matrix
        for (int[] q : queries) {
            int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
            
            mat[r1][c1]++;
            
            if (c2 + 1 < n) {
                mat[r1][c2 + 1]--;
            }
            if (r2 + 1 < n) {
                mat[r2 + 1][c1]--;
            }
            if (r2 + 1 < n && c2 + 1 < n) {
                mat[r2 + 1][c2 + 1]++;
            }
        }
        
        // Step 2: Reconstruct the matrix from the differences using 2D prefix sums
        // First pass: row-wise prefix sums
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                mat[i][j] += mat[i][j - 1];
            }
        }
        
        // Second pass: column-wise prefix sums
        for (int j = 0; j < n; j++) {
            for (int i = 1; i < n; i++) {
                mat[i][j] += mat[i - 1][j];
            }
        }
        
        return mat;
    }
}
```
### Algorithm
- Initialize an `n x n` matrix `mat` with all zeros. This matrix will be used as a difference array.
- For each query `[r1, c1, r2, c2]`, update four points in the `mat`:
  - `mat[r1][c1]++`
  - `mat[r1][c2 + 1]--` (if `c2 + 1 < n`)
  - `mat[r2 + 1][c1]--` (if `r2 + 1 < n`)
  - `mat[r2 + 1][c2 + 1]++` (if `r2 + 1 < n` and `c2 + 1 < n`)
- After processing all queries, transform the difference matrix `mat` into the final result matrix using 2D prefix sums.
- First, calculate prefix sums for each row: `mat[i][j] += mat[i][j-1]`.
- Then, calculate prefix sums for each column: `mat[i][j] += mat[i-1][j]`.
- Return the modified `mat`.

# Solutions
### Java

```java
class Solution {
public
  int[][] rangeAddQueries(int n, int[][] queries) {
    int[][] mat = new int[n][n];
    for (var q : queries) {
      int x1 = q[0], y1 = q[1], x2 = q[2], y2 = q[3];
      mat[x1][y1]++;
      if (x2 + 1 < n) {
        mat[x2 + 1][y1]--;
      }
      if (y2 + 1 < n) {
        mat[x1][y2 + 1]--;
      }
      if (x2 + 1 < n && y2 + 1 < n) {
        mat[x2 + 1][y2 + 1]++;
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i > 0) {
          mat[i][j] += mat[i - 1][j];
        }
        if (j > 0) {
          mat[i][j] += mat[i][j - 1];
        }
        if (i > 0 && j > 0) {
          mat[i][j] -= mat[i - 1][j - 1];
        }
      }
    }
    return mat;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> rangeAddQueries(int n, vector<vector<int>> &queries) {
    vector<vector<int>> mat(n, vector<int>(n));
    for (auto &q : queries) {
      int x1 = q[0], y1 = q[1], x2 = q[2], y2 = q[3];
      mat[x1][y1]++;
      if (x2 + 1 < n) {
        mat[x2 + 1][y1]--;
      }
      if (y2 + 1 < n) {
        mat[x1][y2 + 1]--;
      }
      if (x2 + 1 < n && y2 + 1 < n) {
        mat[x2 + 1][y2 + 1]++;
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i > 0) {
          mat[i][j] += mat[i - 1][j];
        }
        if (j > 0) {
          mat[i][j] += mat[i][j - 1];
        }
        if (i > 0 && j > 0) {
          mat[i][j] -= mat[i - 1][j - 1];
        }
      }
    }
    return mat;
  }
};

```

### Python

```python
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

```