Subrectangle Queries

medium design matrix brute force

Problem

Build a class SubrectangleQueries over a rows × cols integer matrix supporting two operations. updateSubrectangle(row1, col1, row2, col2, newValue) overwrites every cell inside the rectangle with corners (row1, col1) (top-left) and (row2, col2) (bottom-right) with newValue. getValue(row, col) returns the current value at (row, col). With at most 500 calls, the brute-force overwrite is fast enough.

Inputrectangle = [[1,2,1],[4,3,4],[3,2,1],[1,1,1]]

Calls

getValue(0,2), updateSubrectangle(0,0,3,2,5), getValue(0,2), getValue(3,1), updateSubrectangle(3,0,3,2,10), getValue(3,1), getValue(0,2)

Output[1, 5, 5, 10, 5]

First update paints the whole grid to 5; the second repaints only the last row to 10, so (3,1)=10 while (0,2)=5.

rectangle (rows separated by ;, cells by ,)

operations (U r1 c1 r2 c2 v | G r c, comma-separated)

class SubrectangleQueries:
    def __init__(self, rectangle):
        self.rect = rectangle              # keep a reference to the grid

    def updateSubrectangle(self, row1, col1, row2, col2, newValue):
        for r in range(row1, row2 + 1):    # walk every row in the box
            for c in range(col1, col2 + 1):  # and every column
                self.rect[r][c] = newValue   # overwrite the cell

    def getValue(self, row, col):
        return self.rect[row][col]         # O(1) point lookup

class SubrectangleQueries {
  constructor(rectangle) {
    this.rect = rectangle;                 // keep a reference to the grid
  }
  updateSubrectangle(row1, col1, row2, col2, newValue) {
    for (let r = row1; r <= row2; r++)     // walk every row in the box
      for (let c = col1; c <= col2; c++)   // and every column
        this.rect[r][c] = newValue;        // overwrite the cell
  }
  getValue(row, col) {
    return this.rect[row][col];            // O(1) point lookup
  }
}

class SubrectangleQueries {
    private int[][] rect;
    public SubrectangleQueries(int[][] rectangle) {
        rect = rectangle;                  // keep a reference to the grid
    }
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for (int r = row1; r <= row2; r++)     // walk every row in the box
            for (int c = col1; c <= col2; c++) // and every column
                rect[r][c] = newValue;         // overwrite the cell
    }
    public int getValue(int row, int col) {
        return rect[row][col];             // O(1) point lookup
    }
}

class SubrectangleQueries {
    vector<vector<int>> rect;
public:
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        rect = rectangle;                  // keep a copy of the grid
    }
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for (int r = row1; r <= row2; r++)     // walk every row in the box
            for (int c = col1; c <= col2; c++) // and every column
                rect[r][c] = newValue;         // overwrite the cell
    }
    int getValue(int row, int col) {
        return rect[row][col];             // O(1) point lookup
    }
};

Explanation

This is a classic brute-force design problem. Because the constraints are tiny — at most 500 total calls and a grid no larger than 100×100 — we do not need any clever bookkeeping. We simply store the matrix and mutate it directly.

getValue(row, col) is trivial: return rect[row][col] in O(1). All the real work lives in updateSubrectangle.

An update walks the two nested ranges row1..row2 and col1..col2 (both inclusive) and writes newValue into every cell. A single update therefore costs O((row2−row1+1) × (col2−col1+1)), bounded by the grid size. With at most 500 updates over a 100×100 grid that is well within limits.

Order matters: a later update fully overwrites whatever an earlier update wrote in the overlapping cells. In Example 1 the first call paints the entire 4×3 grid to 5; the second call only touches the last row, repainting it to 10. So getValue(3,1) sees 10 while getValue(0,2) still sees 5.

An alternative that trades update speed for query speed is to not mutate the grid at all: store every update as a record (row1,col1,row2,col2,newValue), then getValue scans the updates from newest to oldest and returns the first one whose box contains the point, falling back to the original grid. That makes updates O(1) but queries O(number of updates). Both pass here; the direct-overwrite version shown is the simplest.

Time: update O(area), getValue O(1) Space: O(rows · cols)