Subrectangle Queries
MedPrompt
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)
- Updates all values with
newValuein the subrectangle whose upper left coordinate is(row1,col1)and bottom right coordinate is(row2,col2).
2. getValue(int row, int col)
- Returns the current value of the coordinate
(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 5Example 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:
- There will be at most
500operations considering both methods:updateSubrectangleandgetValue. 1 <= rows, cols <= 100rows == rectangle.lengthcols == rectangle[i].length0 <= row1 <= row2 < rows0 <= col1 <= col2 < cols1 <= newValue, rectangle[i][j] <= 10^90 <= row < rows0 <= col < cols
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves directly modifying the underlying matrix for each update operation. The updateSubrectangle method iterates through all the cells in the specified subrectangle and changes their values. The getValue method simply retrieves the value from the stored matrix.
Algorithm
- Initialize a 2D array
rectanglein the constructor with the given input matrix. - For
updateSubrectangle, use two nested loops to traverse the subrectangle from(row1, col1)to(row2, col2). - In the inner loop, set the value of the current cell
rectangle[i][j]tonewValue. - For
getValue, directly access and return the value atrectangle[row][col].
Walkthrough
In this approach, we store the rectangle as a 2D array. When an update is requested, we iterate over all the cells in the given subrectangle and set their value to the new value. When a value is requested, we simply return the value at the given coordinates from our stored 2D array.
Algorithm:
- Constructor
SubrectangleQueries(rectangle): Store the inputrectanglein a member variable. updateSubrectangle(row1, col1, row2, col2, newValue): Use nested loops to iterate fromi = row1torow2andj = col1tocol2. In each iteration, setrectangle[i][j] = newValue.getValue(row, col): Returnrectangle[row][col].
Code Snippet:
class SubrectangleQueries { private int[][] rectangle; public SubrectangleQueries(int[][] rectangle) { this.rectangle = rectangle; } public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) { for (int i = row1; i <= row2; i++) { for (int j = col1; j <= col2; j++) { this.rectangle[i][j] = newValue; } } } public int getValue(int row, int col) { return this.rectangle[row][col]; }}Complexity
Time
`updateSubrectangle`: O(N * M), where N is `row2 - row1 + 1` and M is `col2 - col1 + 1`. In the worst case, this is O(rows * cols). `getValue`: O(1).
Space
O(rows * cols) to store the matrix. This space is inherent to the problem statement.
Trade-offs
Pros
Simple to implement and understand.
The
getValueoperation is very fast (constant time).
Cons
The
updateSubrectangleoperation can be slow for large subrectangles, making it inefficient if updates are frequent or cover large areas.
This approach optimizes the updateSubrectangle operation by delaying the actual updates. Instead of modifying the matrix, it records each update operation in a list. When getValue is called, it checks this history of updates in reverse order to find the most recent value for the requested cell. If no update covers the cell, the original value is returned.
Algorithm
- In the constructor, store the initial
rectangleand initialize an empty listhistory. - For
updateSubrectangle, add a new entry to thehistorylist containing the update parameters (row1,col1,row2,col2,newValue). - For
getValue(row, col), iterate through thehistorylist from the end to the beginning. - For each recorded update, check if
(row, col)is within the update's boundaries. - If it is, return the
newValuefrom that update and stop the search. - If the loop completes without finding a relevant update, return the original value from
rectangle[row][col].
Walkthrough
This method avoids costly updates to the matrix by storing the update operations themselves. We keep the original matrix and a list of all updateSubrectangle calls.
Algorithm:
- Constructor
SubrectangleQueries(rectangle): Store the inputrectangleand initialize an empty list to store update records. updateSubrectangle(row1, col1, row2, col2, newValue): Create a record of the update (e.g., an array[row1, col1, row2, col2, newValue]) and append it to the list of updates. This is a very fast operation.getValue(row, col): To find the current value, we must consider the updates. Since later updates can override earlier ones, we check the updates in reverse chronological order (from last to first). We iterate through our list of updates from the end. For each update, we check if the given(row, col)is within the update's subrectangle. The first one we find determines the value, so we return itsnewValue. If we check all updates and none cover the cell, we return the value from the original matrix.
Code Snippet:
import java.util.ArrayList;import java.util.List; class SubrectangleQueries { private int[][] rectangle; private List<int[]> history; public SubrectangleQueries(int[][] rectangle) { this.rectangle = rectangle; this.history = new ArrayList<>(); } public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) { history.add(new int[]{row1, col1, row2, col2, newValue}); } public int getValue(int row, int col) { for (int i = history.size() - 1; i >= 0; i--) { int[] update = history.get(i); int r1 = update[0], c1 = update[1], r2 = update[2], c2 = update[3], val = update[4]; if (row >= r1 && row <= r2 && col >= c1 && col <= c2) { return val; } } return rectangle[row][col]; }}Complexity
Time
`updateSubrectangle`: O(1). `getValue`: O(K), where K is the number of `updateSubrectangle` calls made so far.
Space
O(rows * cols + K), where K is the number of updates. This includes O(rows * cols) for the initial matrix and O(K) to store the history of updates.
Trade-offs
Pros
The
updateSubrectangleoperation is extremely fast (constant time).Overall more efficient given the problem constraints, especially when there are many update operations.
Cons
The
getValueoperation's performance degrades as the number of updates increases.Requires extra space proportional to the number of updates.
Solutions
Solution
class SubrectangleQueries { private int [][] g ; private LinkedList < int []> ops = new LinkedList <>(); public SubrectangleQueries ( int [][] rectangle ) { g = rectangle ; } public void updateSubrectangle ( int row1 , int col1 , int row2 , int col2 , int newValue ) { ops . addFirst ( new int [] { row1 , col1 , row2 , col2 , newValue }); } public int getValue ( int row , int col ) { for ( var op : ops ) { if ( op [ 0 ] <= row && row <= op [ 2 ] && op [ 1 ] <= col && col <= op [ 3 ]) { return op [ 4 ]; } } return g [ row ][ col ]; } } /** * Your SubrectangleQueries object will be instantiated and called as such: * SubrectangleQueries obj = new SubrectangleQueries(rectangle); * obj.updateSubrectangle(row1,col1,row2,col2,newValue); * int param_2 = obj.getValue(row,col); */class SubrectangleQueries { public: vector < vector < int >> g ; vector < vector < int >> ops ; SubrectangleQueries ( vector < vector < int >>& rectangle ) { g = rectangle ; } void updateSubrectangle ( int row1 , int col1 , int row2 , int col2 , int newValue ) { ops . push_back ({ row1 , col1 , row2 , col2 , newValue }); } int getValue ( int row , int col ) { for ( int i = ops . size () - 1 ; ~ i ; -- i ) { auto op = ops [ i ]; if ( op [ 0 ] <= row && row <= op [ 2 ] && op [ 1 ] <= col && col <= op [ 3 ]) { return op [ 4 ]; } } return g [ row ][ col ]; } }; /** * Your SubrectangleQueries object will be instantiated and called as such: * SubrectangleQueries* obj = new SubrectangleQueries(rectangle); * obj->updateSubrectangle(row1,col1,row2,col2,newValue); * int param_2 = obj->getValue(row,col); */class SubrectangleQueries : def __init__ ( self , rectangle : List [ List [ int ]]): self . g = rectangle self . ops = [] def updateSubrectangle ( self , row1 : int , col1 : int , row2 : int , col2 : int , newValue : int ) -> None : self . ops . append (( row1 , col1 , row2 , col2 , newValue )) def getValue ( self , row : int , col : int ) -> int : for r1 , c1 , r2 , c2 , v in self . ops [:: - 1 ]: if r1 <= row <= r2 and c1 <= col <= c2 : return v return self . g [ row ][ col ] # Your SubrectangleQueries object will be instantiated and called as such: # obj = SubrectangleQueries(rectangle) # obj.updateSubrectangle(row1,col1,row2,col2,newValue) # param_2 = obj.getValue(row,col)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.