1476. Subrectangle Queries

MediumDesignArrayMatrix
Leetcode Link

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:

  1. 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).

  2. 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 Evaluator

Example 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]])
  1. We perform an update on the subrectangle from (0, 0) to (1, 1) with a new value of 10. 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.

  1. 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.

  1. Let's add another update, changing the value of the subrectangle from (1, 1) to (2, 2) to 20:
1subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20)

Again, this updates the operation list but leaves the grid unchanged.

  1. Another call to getValue for the coordinate (1, 1) would now return 20, as this is the newest value for that location due to the latest update.
1value = subrectangleQueries.getValue(1, 1)
  1. If we ask for the value at (2, 0), which has not been touched by any update operations, the getValue method finds that there are no updates affecting it and thus returns the original value 7 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 is O(1) since it's simply storing the reference to rectangle and initializing an empty list ops.

  • updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None: This method records an update operation by appending a tuple to the ops list representing the subrectangle update parameters. The time complexity for each update is O(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 the ops list in reverse to find the most recent update that covers the cell in question. If k is the number of updates, the worst time complexity is O(k) because it might need to inspect every update in the worst case.

Space Complexity

  • The space complexity for maintaining the rectangle is O(m * n), where m is the number of rows and n is the number of columns in the given rectangle, since it stores the entire grid.

  • The space complexity for maintaining the ops list is O(u), where u is the number of update operations made. Each operation is stored as a tuple with five integers, so the total space taken by ops is proportional to the number of updates.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)


Recommended Readings

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.