1476. Subrectangle Queries
Problem Description
In this problem, we are asked to implement a class called SubrectangleQueries
which encapsulates a 2D rectangle grid of integers provided during instantiation. The class needs to support two operations:
-
updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
: This method allows updating all values within a specified subrectangle to a new given value. The subrectangle to be updated is defined by its upper left coordinate(row1, col1)
and its bottom right coordinate(row2, col2)
. -
getValue(int row, int col)
: This method retrieves the current value at a specific coordinate(row, col)
in the rectangle.
These methods must efficiently reflect any updates made by updateSubrectangle
when getValue
is called.
Intuition
The naive approach to solve the updateSubrectangle
operation would be to iterate over every cell in the subrectangle and update it to newValue
. However, this could become inefficient when there are many updates before a call to getValue
, especially if the subrectangle being updated is large.
To optimize this, we can use an approach where we track only the updates made rather than applying them immediately to the entire subrectangle. Whenever an update operation is performed, we record the details of the update—the coordinates of the subrectangle and the new value—in a list of operations, ops
.
Then, when getValue
is invoked for a specific cell, we iterate through the list of updates in reverse chronological order (latest operation first) because the most recent value is what we’re interested in. We check if the queried cell falls within the subrectangle of an update. If it does, we return the newValue
from the first update operation that includes the cell. Otherwise, if no update operations include the cell, we return the original value of the cell from the initial rectangle grid.
This approach is more efficient in scenarios where there are multiple updates and fewer getValue
calls, as it avoids unnecessary updates to the entire subrectangle when the value of only a few cells might be retrieved later.
Solution Approach
The solution for the SubrectangleQueries
class leverages a key concept in programming known as lazy updating combined with the use of a history list to save update operations. Let's break down the two primary methods provided by the solution.
When the class is initialized with a 2D array representing the rectangle, we store this array and initialize an empty list self.ops
to record update operations:
1def __init__(self, rectangle: List[List[int]]):
2 self.g = rectangle
3 self.ops = []
The updateSubrectangle
method doesn't modify the original grid immediately. Instead, it appends the update information as a tuple (row1, col1, row2, col2, newValue)
to self.ops
:
1def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
2 self.ops.append((row1, col1, row2, col2, newValue))
During the getValue
method, we iterate backward through self.ops
to check if the given row
and col
coordinates fall within any of the recorded subrectangles. If they do, it means that this was the last update that touched the cell before the getValue
request, and the newValue
from that update is returned immediately without checking earlier updates:
1def getValue(self, row: int, col: int) -> int:
2 for r1, c1, r2, c2, v in self.ops[::-1]:
3 if r1 <= row <= r2 and c1 <= col <= c2:
4 return v
5 return self.g[row][col]
This approach is an application of the lazy evaluation pattern, as the updates to the grid are deferred and only evaluated when needed. By applying this strategy, the algorithm ensures that unnecessary cell updates are avoided, reducing the number of operations to be O(1) for each updateSubrectangle
call, and O(k) for each getValue
call, where k is the number of update operations.
In conclusion, the solution approach utilizes a history list mechanism to deftly manage multiple updates and retrieve operations without redundantly modifying the entire rectangle upon each update. This way, the process becomes markedly more efficient for scenarios involving many update operations and relatively few reads.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach for the SubrectangleQueries
class. Suppose we initialize our SubrectangleQueries
class with the following 2D rectangle grid:
11 2 3 24 5 6 37 8 9
The grid is instantiated as:
1subrectangleQueries = SubrectangleQueries([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
- We perform an update on the subrectangle from
(0, 0)
to(1, 1)
with a new value of10
. Our update call will be like this:
1subrectangleQueries.updateSubrectangle(0, 0, 1, 1, 10)
This will not change the grid immediately but will record this operation in self.ops
.
- If we now call the
getValue
method to retrieve the value at(0, 1)
, which is part of the recently updated subrectangle, the method will do the following:
1value = subrectangleQueries.getValue(0, 1)
Since the most recent update included this cell with coordinates (0, 1)
, the method will return 10
, which was the new value set for that subrectangle.
- Let's add another update, changing the value of the subrectangle from
(1, 1)
to(2, 2)
to20
:
1subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20)
Again, this updates the operation list but leaves the grid unchanged.
- Another call to
getValue
for the coordinate(1, 1)
would now return20
, as this is the newest value for that location due to the latest update.
1value = subrectangleQueries.getValue(1, 1)
- If we ask for the value at
(2, 0)
, which has not been touched by any update operations, thegetValue
method finds that there are no updates affecting it and thus returns the original value7
from the original grid:
1value = subrectangleQueries.getValue(2, 0)
Throughout the example, we see that the updateSubrectangle
method appends update operation details to the self.ops
list but doesn't alter the original grid itself. When retrieving a value with getValue
, the method checks the updates in reverse chronological order to see if they affect the cell in question. If they do, the latest value is returned. If not, the original grid value is returned. This optimization allows efficient handling of updates and retrievals by deferring actual updates until needed.
Solution Implementation
1class SubrectangleQueries:
2 def __init__(self, rectangle: List[List[int]]):
3 self.grid = rectangle # Initialize the grid with the given rectangle
4 self.updates = [] # Keep a list to record all the updates made
5
6 def updateSubrectangle(
7 self, row1: int, col1: int, row2: int, col2: int, newValue: int
8 ) -> None:
9 # Record the details of the update operation in the updates list
10 self.updates.append((row1, col1, row2, col2, newValue))
11
12 def getValue(self, row: int, col: int) -> int:
13 # Iterate over the updates in reverse order (most recent first)
14 for r1, c1, r2, c2, value in reversed(self.updates):
15 # If the cell (row, col) is within the updated subrectangle, return the new value
16 if r1 <= row <= r2 and c1 <= col <= c2:
17 return value
18 # If there are no updates that affect the cell, return the original value
19 return self.grid[row][col]
20
21
22# Example of how the SubrectangleQueries class is instantiated and used:
23# obj = SubrectangleQueries(rectangle)
24# obj.updateSubrectangle(row1, col1, row2, col2, newValue)
25# param_2 = obj.getValue(row, col)
26```
27
28Remember that when using this code, you must also have the appropriate imports at the beginning of your script:
29
30```python
31from typing import List
32
1class SubrectangleQueries {
2 private int[][] grid; // Matrix to represent the initial rectangle
3 private LinkedList<int[]> updateOperations = new LinkedList<>(); // List to keep track of update operations
4
5 // Constructor to initialize SubrectangleQueries with a rectangle
6 public SubrectangleQueries(int[][] rectangle) {
7 grid = rectangle;
8 }
9
10 // Method to update a subrectangle.
11 // (row1, col1) is the top left corner and (row2, col2) is the bottom right corner of the subrectangle.
12 // newValue is the value to be updated in the subrectangle.
13 public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
14 // Store the operation details at the beginning of the list for latest priority
15 updateOperations.addFirst(new int[] { row1, col1, row2, col2, newValue });
16 }
17
18 // Method to get the value of the cell at the specified row and column.
19 public int getValue(int row, int col) {
20 // Iterate over the operations in reverse order (start with the most recent one)
21 for (int[] op : updateOperations) {
22 // Check if the current cell was affected by the operation
23 if (op[0] <= row && row <= op[2] && op[1] <= col && col <= op[3]) {
24 return op[4]; // return the updated value if found
25 }
26 }
27 // If no operations affected the cell, return the original value
28 return grid[row][col];
29 }
30}
31
32/**
33 * The following is how you may instantiate and invoke methods of the SubrectangleQueries class:
34 * SubrectangleQueries obj = new SubrectangleQueries(rectangle);
35 * obj.updateSubrectangle(row1, col1, row2, col2, newValue);
36 * int val = obj.getValue(row, col);
37 */
38
1#include <vector>
2using namespace std;
3
4// Class to handle subrectangle queries on a 2D array
5class SubrectangleQueries {
6private:
7 vector<vector<int>> grid; // 2D vector to represent the initial rectangle
8 vector<vector<int>> operations; // List of operations for updates
9
10public:
11 // Constructor that initializes the class with a rectangle
12 SubrectangleQueries(vector<vector<int>>& rectangle) {
13 grid = rectangle;
14 }
15
16 // Updates the values of all cells in a subrectangle
17 void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
18 // Add the update operation to the list of operations
19 operations.push_back({row1, col1, row2, col2, newValue});
20 }
21
22 // Gets the current value of a cell after applying the updates
23 int getValue(int row, int col) {
24 // Loop through the operations in reverse order
25 for (int i = operations.size() - 1; i >= 0; --i) {
26 auto& op = operations[i];
27 // Check if the current cell is within the subrectangle bounds of a previous update
28 if (op[0] <= row && row <= op[2] && op[1] <= col && col <= op[3]) {
29 // If so, return the updated value for this cell
30 return op[4];
31 }
32 }
33 // If no updates affected this cell, return the original value
34 return grid[row][col];
35 }
36};
37
38/**
39 * How to use the class:
40 * SubrectangleQueries* obj = new SubrectangleQueries(rectangle);
41 * obj->updateSubrectangle(row1, col1, row2, col2, newValue);
42 * int value = obj->getValue(row, col);
43 *
44 * Note: You may wrap the usage within a main function if needed.
45 */
46
1// Define the rectangle grid and the operations log as global variables.
2let rectangleGrid: number[][];
3let opsLog: number[][];
4
5// Initial setup for the rectangle grid.
6function setupRectangle(rectangle: number[][]): void {
7 rectangleGrid = rectangle;
8 opsLog = [];
9}
10
11// Update a sub rectangle within the rectangle grid by logging the operation.
12function updateSubrectangle(
13 topLeftRow: number,
14 topLeftCol: number,
15 bottomRightRow: number,
16 bottomRightCol: number,
17 newValue: number,
18): void {
19 opsLog.push([topLeftRow, topLeftCol, bottomRightRow, bottomRightCol, newValue]);
20}
21
22// Get the current value of a cell in the rectangle grid, taking into account any updates.
23function getValueAt(row: number, col: number): number {
24 // Iterate through the operations log in reverse order to find the most recent update affecting the cell.
25 for (let i = opsLog.length - 1; i >= 0; --i) {
26 const [r1, c1, r2, c2, value] = opsLog[i];
27 // Check if the cell lies within the bounds of the current operation.
28 if (r1 <= row && row <= r2 && c1 <= col && col <= c2) {
29 return value;
30 }
31 }
32 // If no operations affect the cell, return the original value from the grid.
33 return rectangleGrid[row][col];
34}
35
36// Example Usage:
37// setupRectangle([[1, 2], [3, 4]]);
38// updateSubrectangle(0, 0, 1, 1, 5);
39// console.log(getValueAt(0, 0)); // Should output the updated value 5.
40
Time and Space Complexity
Time Complexity
-
__init__(self, rectangle: List[List[int]])
: This method initializes the object with the given rectangle. The time complexity isO(1)
since it's simply storing the reference torectangle
and initializing an empty listops
. -
updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None
: This method records an update operation by appending a tuple to theops
list representing the subrectangle update parameters. The time complexity for each update isO(1)
because appending to a list in Python is an amortized constant time operation. -
getValue(self, row: int, col: int) -> int
: This method retrieves the value of the cell at the specified row and column. It iterates over theops
list in reverse to find the most recent update that covers the cell in question. Ifk
is the number of updates, the worst time complexity isO(k)
because it might need to inspect every update in the worst case.
Space Complexity
-
The space complexity for maintaining the
rectangle
isO(m * n)
, wherem
is the number of rows andn
is the number of columns in the given rectangle, since it stores the entire grid. -
The space complexity for maintaining the
ops
list isO(u)
, whereu
is the number of update operations made. Each operation is stored as a tuple with five integers, so the total space taken byops
is proportional to the number of updates.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.