MediumNo. 1476
Subrectangle Queries — LeetCode 1476 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Design, Array, Matrix
- Reading time
- 4 min
- Source
- leetcode.com
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
- Time
- O(m·n)
- Space · auxiliary
- O(1) to O(m·n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0054 | Spiral Matrix | Medium |
| 0059 | Spiral Matrix II | Medium |
| 0289 | Game of Life | Medium |
| 0498 | Diagonal Traverse | Medium |
| 0566 | Reshape the Matrix | Easy |
| 0661 | Image Smoother | Easy |
Frequently asked questions
- How hard is LeetCode 1476. Subrectangle Queries?
LeetCode 1476. Subrectangle Queries is rated Medium on LeetCode.
- What topics does LeetCode 1476. Subrectangle Queries cover?
LeetCode 1476. Subrectangle Queries is tagged Design, Array and Matrix on LeetCode.