Subrectangle Queries — LeetCode 1476 Python Solution

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

Example

Input

["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"]

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]]);

Python solution

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)

Complexity

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1476. Subrectangle Queries is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems