Increment Submatrices by One

MEDIUM

Description

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] = [row1_i, col1_i, row2_i, col2_i], you should do the following operation:

Add 1 to every element in the submatrix with the top left corner (row1_i, col1_i) and the bottom right corner (row2_i, col2_i). That is, add 1 to mat[x][y] for all row1_i <= x <= row2_i and col1_i <= y <= col2_i.

Return the matrix mat after performing every query.

Example 1:

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:

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 <= 10⁴
0 <= row1_i <= row2_i < n
0 <= col1_i <= col2_i < n

Approaches

Checkout 2 different approaches to solve Increment Submatrices by One. Click on different approaches to view the approach and algorithm in detail.

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.

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.

The brute-force method is the most intuitive way to solve the problem. It follows the problem statement literally.

We start by creating the n x n matrix, mat, and filling it with zeros.
We then loop through the queries array. Each element in this array is another array representing a single query: [row1, col1, row2, col2].
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.
In the body of the inner loop, we simply perform the operation mat[i][j]++.
After the outer loop finishes processing all the queries, the mat will hold the final values, and we return it.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(n^2) - We need to store the `n x n` matrix.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Increment Submatrices by One. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Increment Submatrices by One

Patterns:

Prefix Sum

Data Structures:

ArrayMatrix