Domain 2MediumMEDIUM

Subrectangle Queries

Stores the matrix directly and updates subrectangles by iterating cells, leveraging low operation counts for efficiency.

Domain: medium•Updated: 2026-09-17
#Direct Update#2D Array#O(R*C)#O(rows*cols)

Problem Breakdown

We need to implement a class SubrectangleQueries that manages a 2D grid (matrix) of integers. The core functionality involves two operations: updating values within a rectangular region and retrieving the value at a specific coordinate.

Inputs:

  1. Constructor receives an initial rows×colsrows \times cols matrix.
  2. updateSubrectangle: Takes top-left (row1, col1) and bottom-right (row2, col2), plus a new integer to fill that region.
  3. getValue: Returns the value at specific (row, col).

Outputs:

  • Updates modify internal state; no return value (or null).
  • Queries return an integer.

Constraints & Edge Cases:

  • Total operations (update + get) are limited to 500. This is a critical constraint that dictates our complexity requirements.
  • Grid dimensions up to 100×100100 \times 100.
  • Values fit within standard integers (Python handles large ints automatically).
  • Coordinates provided in updates satisfy row1 <= row2 and col1 <= col2.
  • We must ensure we don’t access indices out of bounds, though constraints guarantee valid inputs.

Intuition

The first thought is to store the matrix directly as a 2D array (list of lists).

Brute Force Analysis: If we implement updates by iterating through every cell in the specified rectangle and changing its value:

  • Update Cost: O(rows×cols)O(rows \times cols) per call.
  • Get Cost: O(1)O(1).

Given there are at most 500 total operations, even if all of them were expensive range updates on a full grid (100×100100 \times 100), the worst-case complexity would be roughly 500×(100×100)=5,000,000500 \times (100 \times 100) = 5,000,000 basic operations. In modern interview contexts, this is well within acceptable time limits for Python (typically allowing ~1-2 seconds of execution).

Why not optimize further? If the number of updates were massive (O(N)O(N) where N→∞N \to \infty), we might consider a 2D Segment Tree or Quadtree to achieve faster queries. However, that adds significant implementation complexity and overhead for no benefit here due to the small operation count constraint. The key insight is recognizing when “simple” data structures are sufficient based on input constraints rather than always reaching for advanced algorithms immediately.

Approach

  1. Initialization: Store the provided matrix in a class attribute (e.g., self.grid). This preserves state across calls.
  2. Update Logic:
    • Iterate through rows from row1 to row2.
    • Inside each row, iterate columns from col1 to col2.
    • Assign the new value directly in place.
  3. Get Logic:
    • Simply return self.grid[row][col].

This approach ensures that updates are reflected immediately for subsequent queries without needing complex reconstruction logic.

Complexity Analysis

  • Time Complexity:
    • Constructor: O(rows×cols)O(rows \times cols) to copy/store the initial matrix.
    • Update: O(R⋅C)O(R \cdot C) where RR is height and CC is width of the rectangle being updated (worst case full grid).
    • Get: O(1)O(1).
  • Space Complexity:
    • O(rows×cols)O(rows \times cols) to store the matrix.

Given the constraint that total operations ≤500\le 500, this approach remains efficient enough without over-engineering with advanced data structures.

Solution

class SubrectangleQueries:

    def __init__(self, rectangle):
        """Initialize the grid."""
        self.grid = rectangle
    
    def updateSubrectangle(self, row1, col1, row2, col2, newValue):
        """Update all values in the subrectangle with newValue."""
        # Iterate through rows from top-left to bottom-right of the region
        for r in range(row1, row2 + 1):
            # Iterate through columns within that row segment
            for c in range(col1, col2 + 1):
                self.grid[r][c] = newValue
    
    def getValue(self, row, col):
        """Return the value at (row, col)."""
        return self.grid[row][col]

# Example usage matching LeetCode format:
# subrectangleQueries = SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]])
# print(subrectangleQueries.getValue(0, 2)) # Output: 1

Edge Cases Handled

  • Valid Coordinate Ranges: The loops in updateSubrectangle rely on the constraint that inputs are valid (row1 <= row2, etc.), preventing index errors.
  • Full Grid Updates: If a rectangle covers the entire matrix, the nested loops handle it correctly without special casing.
  • Single Cell Update: When (row1 == row2) and (col1 == col2), the range logic naturally executes once for that specific cell.
  • Large Values: Python integers automatically scale to accommodate values up to 10910^9 (and beyond), avoiding overflow issues common in fixed-width integer languages like C++ or Java without checks.