2536. Increment Submatrices by One LeetCode Solution

In this guide, you will get 2536. Increment Submatrices by One LeetCode Solution with the best time and space complexity. The solution to Increment Submatrices by One problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Increment Submatrices by One solution in C++
Increment Submatrices by One solution in Java
Increment Submatrices by One solution in Python
Additional Resources

2536. Increment Submatrices by One LeetCode Solution image

Problem Statement of Increment Submatrices by One

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:

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 <= 104
0 <= row1i <= row2i < n
0 <= col1i <= col2i < n

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

2536. Increment Submatrices by One LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
    vector<vector<int>> ans(n, vector<int>(n));
    vector<vector<int>> prefix(n, vector<int>(n + 1));

    for (const vector<int>& query : queries) {
      const int row1 = query[0];
      const int col1 = query[1];
      const int row2 = query[2];
      const int col2 = query[3];
      for (int i = row1; i <= row2; ++i) {
        ++prefix[i][col1];
        --prefix[i][col2 + 1];
      }
    }

    for (int i = 0; i < n; ++i) {
      int sum = 0;
      for (int j = 0; j < n; ++j) {
        sum += prefix[i][j];
        ans[i][j] = sum;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */