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:
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 <= 5001 <= queries.length <= 1040 <= row1i <= row2i < n0 <= col1i <= col2i < nThis approach involves directly iterating over each query and incrementing the submatrices defined by each query one element at a time. The advantage is simplicity, though it may not be optimal for larger matrices.
This code iterates through each provided query, applying a straightforward nested loop over the submatrix defined by each query, incrementing each element directly. This is simple but can be slow for large matrices due to the repeated traversal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * queries.length * n) since for each query we potentially look at n^2 elements.
Space Complexity: O(n^2) for the matrix itself.
This optimized approach involves utilizing a technique akin to prefix sums. By marking only changes at the boundaries of the submatrix, we can later apply a prefix sum over the matrix to effectively accumulate the desired increments.
The optimized C solution uses auxiliary plus signs for boundaries to demarcate increments, followed by a prefix sum application on mat, building the desired output efficiently.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to prefix sum computations.
Space Complexity: O(n^2) for the augmented storage of the matrix.
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: O(n * queries.length * n) since for each query we potentially look at n^2 elements. |
| Prefix Sum Approach (Optimization) | Time Complexity: O(n^2) due to prefix sum computations. |
Maximal Square - Top Down Memoization - Leetcode 221 • NeetCode • 83,339 views views
Watch 9 more video solutions →Practice Increment Submatrices by One with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor