Subrectangle Queries: Design a 2D Matrix Updater

You are given a rectangular matrix of integers. Design a class called SubrectangleQueries that supports two operations: updating every cell in a sub-rectangle to a new value, and querying the value at a specific cell. This is LeetCode 1476: Subrectangle Queries.

Given the matrix [[1,2,1],[4,3,4],[3,2,1],[1,1,1]], here is what the class needs to handle:

• updateSubrectangle(0, 0, 1, 2, 5) sets every cell from row 0, col 0 to row 1, col 2 to the value 5.
• getValue(0, 2) returns 5, because the cell was just updated.
• getValue(3, 1) returns 1, because that cell was outside the update region.

Why this problem matters

Design problems test whether you can translate a specification into clean, working code. Unlike algorithmic puzzles where the trick is finding the right approach, design problems are about building something that works correctly across all operations. You need to think about how data is stored, how operations interact with each other, and what happens when updates overlap.

Subrectangle Queries is a great entry point into design problems because the operations are visual and concrete. You can literally draw what happens on a grid. That makes it easier to reason about correctness compared to more abstract design problems like LRU Cache or Twitter feeds.

The problem also introduces a meaningful optimization choice. The brute-force approach works fine given the constraints, but there is a clever alternative that trades query time for update time. Understanding when each approach is better teaches you to think about operation frequency, a skill that matters in real system design.

The key insight

There are two valid approaches here, and understanding both is valuable.

Approach 1: Direct update. When updateSubrectangle is called, loop through every cell in the sub-rectangle and set it to the new value. When getValue is called, just return rectangle[row][col]. This is simple and works well when queries are frequent relative to updates.

Approach 2: Lazy update with a history log. Instead of modifying the matrix, store each update as a tuple (row1, col1, row2, col2, newValue) in a list. When getValue is called, scan the history list in reverse order. The first update whose rectangle contains the queried cell gives you the answer. If no update covers the cell, return the original matrix value. This approach is faster for updates (O(1) per update) but slower for queries (O(h) where h is the number of updates).

For this problem, the constraints are small enough (at most 500 operations, matrix up to 100x100) that either approach passes comfortably. The brute-force direct update is easier to implement and understand.

The solution

class SubrectangleQueries:
    def __init__(self, rectangle: list[list[int]]):
        self.rect = rectangle

    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.rect[r][c] = newValue

    def getValue(self, row: int, col: int) -> int:
        return self.rect[row][col]

The constructor stores a reference to the input matrix. No copying is needed since we own the data.

The updateSubrectangle method uses two nested loops. The outer loop iterates from row1 to row2 inclusive, and the inner loop iterates from col1 to col2 inclusive. Every cell in that range gets set to newValue. This is as direct as it gets.

The getValue method is a single array lookup. Because we modify the matrix in place during updates, the current value at any cell always reflects the most recent update that touched it.

Visual walkthrough

Let's trace through a sequence of operations on a 4x3 matrix. Watch how update regions overwrite cells and how queries return the current state.

Notice how in Step 5, the second update partially overlaps the first. Cells at (1,1) and (1,2) were set to 5 by the first update and then overwritten to 9 by the second. When you query those cells, you get 9 because the most recent write wins. This is the same behavior you would expect from any mutable data structure.

Complexity analysis

In the direct approach, each update touches r * c cells where r and c are the dimensions of the sub-rectangle. Queries are constant time since they are just an array lookup. Space is the size of the matrix.

In the lazy approach, updates are O(1) because you just append a tuple to a list. Queries are O(h) where h is the total number of updates, since you scan the history in reverse. Space adds h entries on top of the original matrix.

The direct approach is better when you have many queries and few updates. The lazy approach is better when you have many updates but few queries, since it avoids doing unnecessary work in sub-rectangles that might be overwritten before anyone reads them.

The building blocks

1. In-place sub-rectangle fill

The core operation is filling a rectangular region of a 2D array with a single value:

for r in range(row1, row2 + 1):
    for c in range(col1, col2 + 1):
        matrix[r][c] = value

This two-loop pattern shows up in any problem that involves rectangular regions: setting pixels, clearing areas, or initializing sub-grids. The key detail is using inclusive bounds on both ends, which means row2 + 1 and col2 + 1 in the range calls.

2. Reverse scan for most-recent-wins semantics

When multiple updates can overlap, scanning a history list in reverse gives you the most recent update first:

for i in range(len(history) - 1, -1, -1):
    r1, c1, r2, c2, val = history[i]
    if r1 <= row <= r2 and c1 <= col <= c2:
        return val

This is the same idea behind undo stacks, version histories, and write-ahead logs. The last write to a location is the current value. By scanning backwards, you can return as soon as you find the first match, skipping all older updates.

3. Point-in-rectangle containment check

Checking whether a point (row, col) falls inside a rectangle defined by (row1, col1, row2, col2):

row1 <= row <= row2 and col1 <= col <= col2

This four-way bounds check is a fundamental geometric primitive. You will use it in collision detection, spatial queries, and any problem involving rectangular regions. Make sure all four inequalities are non-strict (using <=) since the rectangle boundaries are inclusive.

Edge cases

• Single cell update: updateSubrectangle(r, c, r, c, val) is valid. The loops run once each, setting exactly one cell.
• Full matrix update: when the sub-rectangle covers the entire matrix, every cell gets the same value. The loops iterate over every row and column.
• Overlapping updates: later updates overwrite earlier ones. The last update to touch a cell determines its value.
• Query before any update: returns the original value from the constructor. No updates have modified the matrix yet.
• Same value update: updating a region to its current value is a no-op in terms of output, but the loops still run. The lazy approach handles this efficiently since it just appends a record.
• 1x1 matrix: the smallest possible matrix. All operations work correctly because the loops handle single-element ranges.

From understanding to recall

The direct approach is easy to understand: two nested loops fill a region, and a single lookup answers a query. But when you sit down to code it in an interview, the details matter. Do you use inclusive or exclusive bounds? Do you iterate rows then columns or the reverse? Do you need to copy the matrix in the constructor?

These are not hard questions when you are reading a solution. They are hard when you are writing one from scratch with someone watching. Spaced repetition turns this kind of pattern knowledge into reflex. You practice writing the sub-rectangle fill loop a few times, and the range(row1, row2 + 1) pattern becomes automatic. No more second-guessing the bounds.

Related posts

• Design Memory Allocator - Another design problem where you simulate operations on a linear data structure
• Set Matrix Zeroes - A matrix manipulation problem that requires careful in-place modification of rows and columns
• Reshape the Matrix - Rearranging matrix elements while preserving row-major order