1476.Subrectangle_Queries(Medium).md

1476. Subrectangle Queries (Medium)

Date and Time: Jun 13, 2026

Link: https://leetcode.com/problems/subrectangle-queries/

Question:

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 lower 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],[1,1,2,1,10],[1,1],[2,1]]
Output: [null,1,null,5,5,null,10,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,0]]
Output: [null,1,null,100,100,null,3]

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

• 0 <= col <= cols - 1

Walk-through:

Store the rectangle directly. updateSubrectangle iterates over the sub-rectangle and sets every cell to newValue. getValue is a direct index lookup.

Python Solution:

class SubrectangleQueries:

    def __init__(self, rectangle: List[List[int]]):
        self.rectangle = rectangle
        
    # Directly update from rectanlge
    # TC: O((row1-row2) * (col1-col2))
    def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
        for r in range(row1, row2+1):
            for c in range(col1, col2+1):
                self.rectangle[r][c] = newValue
        
    # Directly access from rectangle, TC: O(1)
    def getValue(self, row: int, col: int) -> int:
        return self.rectangle[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)

Time Complexity: updateSubrectangle: $O((r_2 - r_1) \cdot (c_2 - c_1))$; getValue: $O(1)$.
Space Complexity: $O(1)$ extra space; the rectangle is stored in-place.