LeetCode 1476 - Subrectangle Queries

Difficulty: 🟡 Medium
Topics: Array, Design, Matrix

Solution

Problem Understanding

The problem asks us to design a class called SubrectangleQueries that operates on a two dimensional integer matrix, referred to as a rectangle. This class must support two operations efficiently:

The first operation, updateSubrectangle(row1, col1, row2, col2, newValue), modifies a rectangular region inside the matrix. Every element whose coordinates fall within the specified top left corner (row1, col1) and bottom right corner (row2, col2) must be replaced with newValue.

The second operation, getValue(row, col), returns the current value stored at a specific coordinate in the rectangle.

In simpler terms, we are maintaining a mutable matrix where rectangular portions may be updated repeatedly, and individual cells may be queried at any time.

The input consists of a matrix passed into the constructor. Each row contains integers, and the matrix dimensions are bounded by 100 x 100. Once the object is created, a sequence of update and query operations will be performed.

The expected output for getValue() is straightforward, it must return whatever value currently exists at the requested coordinate after all previous updates have been applied.

The constraints reveal several important observations:

The matrix dimensions are relatively small, at most 100 x 100, meaning there are at most 10,000 cells.
The total number of operations is at most 500, which is also small.
Updates affect rectangular ranges, but queries only request a single cell.

These constraints suggest that a straightforward solution may already be fast enough. Since the total workload is limited, we do not need advanced data structures such as segment trees, difference arrays, or lazy propagation.

Several edge cases are worth considering upfront. Updates may cover the entire matrix, a single row, a single column, or even just one cell. Multiple overlapping updates can occur, meaning later updates must overwrite earlier ones correctly. The problem guarantees all coordinates are valid, so we do not need bounds checking.

Approaches

Brute Force Approach

The most direct way to solve this problem is to store the matrix exactly as given and physically update every affected cell whenever updateSubrectangle() is called.

For an update operation, we iterate through every row between row1 and row2, and every column between col1 and col2, replacing the value with newValue.

For a query operation, we simply return the value stored at the requested coordinate.

This approach is correct because the matrix is always maintained in its current state. Every update immediately modifies all affected cells, so any later query sees the correct value.

Although this is technically a brute force solution, it performs very well under the given constraints. Since the matrix size is at most 100 x 100, even updating the entire matrix only touches 10,000 cells. With at most 500 operations, the total work remains manageable.

Key Insight for the Optimal Solution

The key observation is that the constraints are intentionally small.

Sometimes matrix update problems require sophisticated optimizations because updates and queries may number in the millions. Here, however, we only have at most 500 operations and a maximum matrix size of 10,000 cells.

Because of this, directly updating the matrix is not only simple but also optimal in practice. Trying to store update histories or use advanced interval structures would complicate the implementation without improving runtime meaningfully.

The best strategy is therefore to maintain the matrix in its current state and overwrite cells directly during updates.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	`O((row2-row1+1) × (col2-col1+1))` per update, `O(1)` query	`O(rows × cols)`	Directly modifies every affected cell
Optimal	`O((row2-row1+1) × (col2-col1+1))` per update, `O(1)` query	`O(rows × cols)`	Same as brute force, constraints make it effectively optimal

Algorithm Walkthrough

Step 1: Store the Rectangle

When the object is initialized, store the input matrix as an instance variable.

We keep a reference to the rectangle so that updates can directly modify it and queries can instantly access values.

Step 2: Handle Rectangle Updates

When updateSubrectangle() is called:

Iterate through rows from row1 to row2, inclusive.
For each row, iterate through columns from col1 to col2, inclusive.
Replace every visited cell with newValue.

We do this because every element inside the specified rectangle must be overwritten.

For example:

Initial matrix:

Calling:

updateSubrectangle(0, 0, 3, 2, 5)

means every cell in rows 0 through 3 and columns 0 through 2 becomes 5.

Result:

Step 3: Handle Queries

When getValue(row, col) is called:

Access the matrix directly at rectangle[row][col].
Return the value.

Since the matrix is always kept updated, no additional processing is required.

Why it works

The core invariant is that the matrix stored inside the object always reflects the latest state after all updates.

Whenever an update occurs, every affected cell is immediately overwritten. Therefore, any future query simply reads the value directly from the matrix, guaranteeing correctness. Since updates overwrite previous values in order, later updates naturally take precedence over earlier ones.

Python Solution

from typing import List

class SubrectangleQueries:

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

    def updateSubrectangle(
        self,
        row1: int,
        col1: int,
        row2: int,
        col2: int,
        newValue: int
    ) -> None:

        for row in range(row1, row2 + 1):
            for col in range(col1, col2 + 1):
                self.rectangle[row][col] = newValue

    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)

The constructor stores the matrix in self.rectangle. Since we need to mutate the matrix over time, keeping it as an instance variable allows all methods to access and modify the same shared state.

The updateSubrectangle() method uses nested loops. The outer loop iterates through all affected rows, while the inner loop iterates through all affected columns. Every cell inside the rectangular range is overwritten with newValue.

The getValue() method is extremely simple because the matrix is always maintained in its latest state. We directly return the requested coordinate in constant time.

This implementation closely follows the algorithm described earlier and takes advantage of the small input constraints.

Go Solution

type SubrectangleQueries struct {
	rectangle [][]int
}

func Constructor(rectangle [][]int) SubrectangleQueries {
	return SubrectangleQueries{
		rectangle: rectangle,
	}
}

func (this *SubrectangleQueries) UpdateSubrectangle(
	row1 int,
	col1 int,
	row2 int,
	col2 int,
	newValue int,
) {
	for row := row1; row <= row2; row++ {
		for col := col1; col <= col2; col++ {
			this.rectangle[row][col] = newValue
		}
	}
}

func (this *SubrectangleQueries) GetValue(row int, col int) int {
	return this.rectangle[row][col]
}

/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * obj := Constructor(rectangle)
 * obj.UpdateSubrectangle(row1, col1, row2, col2, newValue)
 * param_2 := obj.GetValue(row, col)
 */

The Go implementation mirrors the Python solution closely. The matrix is stored as a [][]int field inside the struct.

Since slices in Go are reference-like, updates modify the original underlying data structure directly, which is exactly what we want.

Integer overflow is not a concern because values are bounded by 10^9, well within Go's standard integer range.

Unlike Python, Go requires explicit struct definitions and method receivers. We use pointer receivers for update methods so modifications affect the original object.

Worked Examples

Example 1

Initial rectangle:

Operation	Matrix State / Result
`getValue(0,2)`	Returns `1`
`updateSubrectangle(0,0,3,2,5)`	Entire matrix becomes `5`
`getValue(0,2)`	Returns `5`
`getValue(3,1)`	Returns `5`
`updateSubrectangle(3,0,3,2,10)`	Last row becomes `10 10 10`
`getValue(3,1)`	Returns `10`
`getValue(0,2)`	Returns `5`

After first update:

After second update:

Example 2

Initial rectangle:

1 1 1
2 2 2
3 3 3

Operation	Matrix State / Result
`getValue(0,0)`	Returns `1`
`updateSubrectangle(0,0,2,2,100)`	Entire matrix becomes `100`
`getValue(0,0)`	Returns `100`
`getValue(2,2)`	Returns `100`
`updateSubrectangle(1,1,2,2,20)`	Bottom-right region becomes `20`
`getValue(2,2)`	Returns `20`

After first update:

100 100 100
100 100 100
100 100 100

After second update:

100 100 100
100 20  20
100 20  20

Complexity Analysis

Measure	Complexity	Explanation
Time	`O((row2-row1+1) × (col2-col1+1))` for update, `O(1)` for query	We visit each cell in the target rectangle once
Space	`O(rows × cols)`	We store the matrix

The update operation depends on the size of the affected subrectangle. In the worst case, the entire matrix must be updated, resulting in O(rows × cols) time.

The query operation is constant time because it simply accesses one matrix element.

The space complexity comes from storing the rectangle itself. No extra auxiliary data structures are needed.

Test Cases

# Example 1
obj = SubrectangleQueries([
    [1, 2, 1],
    [4, 3, 4],
    [3, 2, 1],
    [1, 1, 1]
])

assert obj.getValue(0, 2) == 1  # Initial lookup
obj.updateSubrectangle(0, 0, 3, 2, 5)
assert obj.getValue(0, 2) == 5  # Entire matrix updated
assert obj.getValue(3, 1) == 5  # Last row updated
obj.updateSubrectangle(3, 0, 3, 2, 10)
assert obj.getValue(3, 1) == 10  # Last row overwritten
assert obj.getValue(0, 2) == 5  # Earlier rows unchanged

# Example 2
obj = SubrectangleQueries([
    [1, 1, 1],
    [2, 2, 2],
    [3, 3, 3]
])

assert obj.getValue(0, 0) == 1  # Initial state
obj.updateSubrectangle(0, 0, 2, 2, 100)
assert obj.getValue(0, 0) == 100  # Whole matrix update
assert obj.getValue(2, 2) == 100  # Bottom-right updated
obj.updateSubrectangle(1, 1, 2, 2, 20)
assert obj.getValue(2, 2) == 20  # Overlapping update

# Single cell matrix
obj = SubrectangleQueries([[7]])
assert obj.getValue(0, 0) == 7  # Single value
obj.updateSubrectangle(0, 0, 0, 0, 99)
assert obj.getValue(0, 0) == 99  # Single cell update

# Single row update
obj = SubrectangleQueries([
    [1, 2, 3, 4]
])

obj.updateSubrectangle(0, 1, 0, 2, 9)
assert obj.getValue(0, 0) == 1  # Unchanged
assert obj.getValue(0, 1) == 9  # Updated
assert obj.getValue(0, 2) == 9  # Updated
assert obj.getValue(0, 3) == 4  # Unchanged

# Single column update
obj = SubrectangleQueries([
    [1],
    [2],
    [3]
])

obj.updateSubrectangle(0, 0, 2, 0, 8)
assert obj.getValue(0, 0) == 8  # Updated top
assert obj.getValue(2, 0) == 8  # Updated bottom

# Overlapping updates
obj = SubrectangleQueries([
    [1, 1],
    [1, 1]
])

obj.updateSubrectangle(0, 0, 1, 1, 5)
obj.updateSubrectangle(0, 0, 0, 0, 9)

assert obj.getValue(0, 0) == 9  # Later update wins
assert obj.getValue(1, 1) == 5  # Earlier update preserved elsewhere

Test	Why
Example 1	Validates full matrix updates and row overwrite behavior
Example 2	Validates overlapping subrectangle updates
Single cell matrix	Ensures minimum boundary case works
Single row update	Verifies row-only modification
Single column update	Verifies column-only modification
Overlapping updates	Ensures later updates correctly override earlier values

Edge Cases

Entire Matrix Update

One important edge case occurs when the update rectangle spans the entire matrix. A buggy implementation might accidentally miss rows or columns because of off-by-one errors.

Our implementation handles this correctly because both loops are inclusive:

range(row1, row2 + 1)
range(col1, col2 + 1)

This guarantees the bottom boundary is included.

Single Cell Update

Another important case is when row1 == row2 and col1 == col2. This means only one element should change.

Some implementations incorrectly assume a larger rectangle and fail when the range contains only one element. Our nested loops naturally handle this because the ranges still execute exactly once.

Overlapping Updates

Multiple updates may overlap partially or completely. A common source of bugs is failing to preserve update order.

For example:

update(0,0,2,2,100)
update(1,1,2,2,20)

The second update should overwrite only the overlapping region.

Our implementation works correctly because updates directly mutate the matrix in sequence. Later updates naturally replace earlier values where overlaps occur.

Query After Many Updates

A query may occur after many modifications to the matrix.

A lazy implementation that delays updates could accidentally return stale values if synchronization is incorrect. Our solution avoids this entirely because the matrix is always kept fully updated after every operation, making queries constant time and always accurate.