Subrectangle Queries

Medium

Nuro

2 views

Topics:

Arrays

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 newValue in 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 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:

There will be at most 500 operations considering both methods: updateSubrectangle and getValue.
1 <= rows, cols <= 100
rows == rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols

Subrectangle Queries

Medium

Nuro

2 views

Topics:

Arrays

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 newValue in 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 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:

There will be at most 500 operations considering both methods: updateSubrectangle and getValue.
1 <= rows, cols <= 100
rows == rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions of the rectangle and the values within it (e.g., maximum size, negative numbers, zeros)?
If the given subrectangle coordinates for update or query are invalid (e.g., out of bounds, row1 > row2, col1 > col2), what should the behavior be: throw an error, return a default value, or treat it as no-op?
If multiple update operations overlap, how should the queries reflect the order of updates (i.e., should later updates overwrite earlier ones)?
Can I assume the input rectangle is always valid (non-null and rectangular), and row1 <= row2 and col1 <= col2?
What is the expected frequency of updateSubrectangle and getValue operations; is one expected to be significantly more common than the other?

Brute Force Solution

Approach

The brute force approach directly manipulates the given grid of numbers based on the queries. To update a subrectangle, it goes through each cell within the specified rectangle and changes its value. To retrieve the value of a cell, it directly accesses that cell's value in the grid.

Here's how the algorithm would work step-by-step:

To update a subrectangle, visit every single cell within the rectangle you want to change.
For each of these cells, replace its original value with the new value provided in the update.
To retrieve the value of a specific cell, simply look up and return the number stored at that cell's location in the grid.

Code Implementation

class SubrectangleQueries:
    def __init__(self, rectangle):
        self.rectangle = rectangle

    def updateSubrectangle(self, row1, col1, row2, col2, newValue):
        # Iterate through the specified subrectangle
        for row_index in range(row1, row2 + 1):

            # Iterate through columns for the current row
            for column_index in range(col1, col2 + 1):

                # Update the value at the current cell
                self.rectangle[row_index][column_index] = newValue

    def getValue(self, row, col):
        # Retrieve the value at the given row and column
        return self.rectangle[row][col]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The updateSubrectangle operation iterates through all cells within the specified subrectangle. If the subrectangle spans the entire grid, the time complexity would be proportional to the number of rows (m) times the number of columns (n) in the grid. The getValue operation accesses a single cell in the grid, which takes constant time O(1). Therefore, the dominant operation is updateSubrectangle, resulting in a time complexity of O(m*n) in the worst case.

Space Complexity

O(1) – The brute force approach described directly modifies the input grid in place. It does not create any additional data structures like temporary arrays, lists, or hash maps. Only a constant number of variables (e.g., loop counters, the new value for updating) are used regardless of the size of the grid. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The efficient approach is to keep a record of all update operations performed on the rectangle. When querying, we need to traverse these update operations to see which one affected the queried cell the most recently. This avoids modifying the actual matrix directly until absolutely necessary, improving performance for frequent queries and infrequent updates.

Here's how the algorithm would work step-by-step:

When the rectangle is first created, save its initial values.
When an update happens within a subrectangle, save the update's coordinates and the new value.
When a query is made for a specific cell, check if any update operations overlap this cell.
If multiple update operations overlap, find the most recent one.
Return the updated value if found, or the original value if no updates affected the cell.

Code Implementation

class SubrectangleQueries:

    def __init__(self, rectangle):
        self.rectangle = rectangle
        self.update_history = []

    def updateSubrectangle(self, row1, col1, row2, col2, newValue):
        # Store the update operation
        self.update_history.append((row1, col1, row2, col2, newValue))

    def getValue(self, row, col):
        # Iterate through the update history to find the most recent update.
        for index in range(len(self.update_history) - 1, -1, -1):
            row1, col1, row2, col2, newValue = self.update_history[index]
            # Check if the current cell lies within the updated subrectangle.
            if row1 <= row <= row2 and col1 <= col <= col2:
                return newValue

        # If no updates affected the cell, return the original value.
        return self.rectangle[row][col]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m) – The constructor takes O(rows * cols) time to initialize the rectangle, where rows and cols are the dimensions of the input rectangle. The updateSubrectangle method takes O(1) time because it only stores the update parameters. The getValue method iterates through the list of update operations. In the worst-case scenario, it has to iterate through all m update operations to find the most recent update affecting the given row and col. Therefore, the getValue operation has a time complexity of O(m), where m is the number of update operations performed.

Space Complexity

O(U) – The described solution maintains a record of update operations. Each update operation stores the coordinates of the subrectangle that was updated and the new value. Therefore, the space required grows linearly with the number of update operations, U, performed on the rectangle, as we store the coordinates and value for each update. No other significant auxiliary data structures are used. Thus, the auxiliary space complexity is O(U).

Edge Cases

Case	How to Handle
Null or empty rectangle array	Throw an IllegalArgumentException or return without processing as an empty rectangle cannot be updated or queried.
Zero dimensions for the rectangle (e.g., row1 == row2 or col1 == col2)	Treat as a no-op; the update or query skips processing for that invalid rectangle.
row1, col1, row2, or col2 are out of bounds of the rectangle array	Throw an IndexOutOfBoundsException or clip the indices to the valid bounds of the array.
Update value is the same as the original values within the subrectangle	The update operation will still execute, but no actual changes occur in the rectangle array.
Querying a cell after multiple overlapping subrectangle updates	The query should return the value resulting from the last update affecting that cell.
Very large rectangle array causing memory issues	Consider using a sparse matrix representation or paging if the data doesn't fit in memory.
Maximum integer value for the update value	The solution should handle maximum integer value without causing an integer overflow during any calculations.
Many update operations followed by a single query operation	Optimize the update operation to be efficient, since queries will reflect the latest state after all updates.