# Subrectangle Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/subrectangle-queries)
Canonical: https://scaleengineer.com/dsa/problems/subrectangle-queries
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Matrix
**Companies:** [Info Edge](https://scaleengineer.com/companies/info-edge), [Nuro](https://scaleengineer.com/companies/nuro)
---
## Problem
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`

# Approaches
## Brute-force Update
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.
**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.
**Pros:** Simple to implement and understand.; The `getValue` operation is very fast (constant time).
**Cons:** The `updateSubrectangle` operation can be slow for large subrectangles, making it inefficient if updates are frequent or cover large areas.
### Explanation
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:**

1.  **Constructor `SubrectangleQueries(rectangle)`**: Store the input `rectangle` in a member variable.
2.  **`updateSubrectangle(row1, col1, row2, col2, newValue)`**: Use nested loops to iterate from `i = row1` to `row2` and `j = col1` to `col2`. In each iteration, set `rectangle[i][j] = newValue`.
3.  **`getValue(row, col)`**: Return `rectangle[row][col]`.

**Code Snippet:**
```java
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];
    }
}
```
### Algorithm
- Initialize a 2D array `rectangle` in 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]` to `newValue`.
- For `getValue`, directly access and return the value at `rectangle[row][col]`.

## Lazy Update with History
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.
**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.
**Pros:** The `updateSubrectangle` operation is extremely fast (constant time).; Overall more efficient given the problem constraints, especially when there are many update operations.
**Cons:** The `getValue` operation's performance degrades as the number of updates increases.; Requires extra space proportional to the number of updates.
### Explanation
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:**

1.  **Constructor `SubrectangleQueries(rectangle)`**: Store the input `rectangle` and initialize an empty list to store update records.
2.  **`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.
3.  **`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 its `newValue`. If we check all updates and none cover the cell, we return the value from the original matrix.

**Code Snippet:**
```java
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];
    }
}
```
### Algorithm
- In the constructor, store the initial `rectangle` and initialize an empty list `history`.
- For `updateSubrectangle`, add a new entry to the `history` list containing the update parameters (`row1`, `col1`, `row2`, `col2`, `newValue`).
- For `getValue(row, col)`, iterate through the `history` list 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 `newValue` from that update and stop the search.
- If the loop completes without finding a relevant update, return the original value from `rectangle[row][col]`.

# Solutions
### Java

```java
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); */
```

### CPP

```cpp
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); */
```

### Python

```python
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)
```