Watch 8 video solutions for Subrectangle Queries, a medium level problem involving Array, Design, Matrix. This walkthrough by Algorithms and Data Structures Course has 1,980 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |