Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:
1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).2. getValue(int row, int col)
(row,col) from the rectangle.
Example 1:
Input ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"] [[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]] Output [null,1,null,5,5,null,10,5] Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]); // The initial rectangle (4x3) looks like: // 1 2 1 // 4 3 4 // 3 2 1 // 1 1 1 subrectangleQueries.getValue(0, 2); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 5 5 5 subrectangleQueries.getValue(0, 2); // return 5 subrectangleQueries.getValue(3, 1); // return 5 subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 10 10 10 subrectangleQueries.getValue(3, 1); // return 10 subrectangleQueries.getValue(0, 2); // return 5
Example 2:
Input ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"] [[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]] Output [null,1,null,100,100,null,20] Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]); subrectangleQueries.getValue(0, 0); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100); subrectangleQueries.getValue(0, 0); // return 100 subrectangleQueries.getValue(2, 2); // return 100 subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20); subrectangleQueries.getValue(2, 2); // return 20
Constraints:
500 operations considering both methods: updateSubrectangle and getValue.1 <= rows, cols <= 100rows == rectangle.lengthcols == rectangle[i].length0 <= row1 <= row2 < rows0 <= col1 <= col2 < cols1 <= newValue, rectangle[i][j] <= 10^90 <= row < rows0 <= col < colsProblem Overview: You need to design a data structure that stores a matrix and supports two operations: update all values inside a subrectangle and return the value of a specific cell. The challenge is balancing update cost with query performance.
Approach 1: Direct Matrix Update (Update: O((r2-r1+1)*(c2-c1+1)), Query: O(1), Space: O(1))
Store the matrix directly and modify it during every update operation. When updateSubrectangle(row1, col1, row2, col2, newValue) is called, iterate through all rows from row1 to row2 and all columns from col1 to col2, assigning newValue to each cell. The getValue(row, col) operation becomes a constant-time lookup because the matrix always reflects the latest state. This approach is simple and predictable, and it performs well when the number of update operations is small or when rectangles are relatively small.
This method relies only on basic iteration over a matrix and fits naturally with typical array manipulation patterns. The tradeoff is that large rectangle updates can be expensive because every affected cell must be modified immediately.
Approach 2: Lazy Update With Overlays (Update: O(1), Query: O(k), Space: O(k))
Instead of modifying the matrix immediately, store each update as an overlay record containing (row1, col1, row2, col2, value). The base matrix remains unchanged. Each update simply appends a new record to a list, making the update operation constant time.
When getValue(row, col) is called, iterate through the updates in reverse order (most recent first). Check whether the queried cell lies inside any stored rectangle. The first matching update determines the value. If no update covers the cell, return the original matrix value. This technique shifts the cost from updates to queries and demonstrates a common design pattern where writes are cheap and reads resolve the final state lazily.
This approach is efficient when updates are frequent but queries are relatively limited. Because updates are stored rather than applied, memory grows with the number of updates.
Recommended for interviews: The direct matrix update approach is usually the expected solution because it keeps the implementation straightforward and meets the problem constraints. Mentioning the lazy overlay strategy shows deeper system design thinking. It demonstrates that you can trade immediate computation for deferred resolution, which is a common optimization pattern in data structure design.
This approach involves directly modifying the original matrix whenever an update is requested. Each cell in the specified subrectangle is updated with the new value. The getValue function simply retrieves the desired cell value using its coordinates, as the matrix is up-to-date after each operation.
The C solution defines a struct containing a pointer to the rectangle, along with its dimensions. The updateSubrectangle function iterates over the specified subrectangle, updating each value to newValue. The getValue function directly accesses the value at the given coordinates.
The time complexity for updateSubrectangle is O((row2-row1+1) * (col2-col1+1)), or O(m * n) in the worst case. getValue runs in O(1) time. The space complexity is O(1), excluding the input matrix size.
This approach optimizes by recording updates instead of applying them directly to the matrix until getValue is called. Each update stores information about the subrectangle and new value to apply. When retrieving a value, it checks the latest applicable update and applies overlays if needed, optimizing space and computational efficiency for a large number of updates.
The lazy update structure in C uses an array of updates, capturing the operations rather than directly modifying the matrix. It iterates through updates in reverse to check applicability when retrieving a value, allowing efficient accesses without unnecessary updates.
Time complexity of updateSubrectangle is O(1), while getValue has O(U) complexity, where U is the count of updates. Space complexity is O(U).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Direct Matrix Update | The time complexity for |
| Lazy Update With Overlays | Time complexity of |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Matrix Update | Update: O((r2-r1+1)*(c2-c1+1)), Query: O(1) | O(1) | Best when updates are limited or rectangles are small and constant-time queries are required |
| Lazy Update With Overlays | Update: O(1), Query: O(k) | O(k) | Useful when updates are frequent and you want to avoid repeatedly modifying large subrectangles |
LeetCode 1476. Subrectangle Queries Solution Explained - Java • Algorithms and Data Structures Course • 1,980 views views
Watch 7 more video solutions →Practice Subrectangle Queries with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor