Skip to content

1476. Subrectangle Queries 👎

  • Time:
    • Constructor: $O(\texttt{rows} \cdot \texttt{cols})$
    • updateSubrectangle(row1: int, col1: int, row2: int, col2: int, newValue: int): $O(1)$
    • getValue(row: int, col: int): $O(|\texttt{updateSubrectangle()}|)$
  • Space: $O(|\texttt{updateSubrectangle()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class SubrectangleQueries {
 public:
  SubrectangleQueries(vector<vector<int>>& rectangle) : rectangle(rectangle) {}

  void updateSubrectangle(int row1, int col1, int row2, int col2,
                          int newValue) {
    updates.push_back({row1, col1, row2, col2, newValue});
  }

  int getValue(int row, int col) {
    for (int i = updates.size() - 1; i >= 0; --i) {
      auto [r1, c1, r2, c2, v] = updates[i];
      if (r1 <= row && row <= r2 && c1 <= col && col <= c2)
        return v;
    }
    return rectangle[row][col];
  }

 private:
  const vector<vector<int>>& rectangle;
  vector<array<int, 5>> updates;  // [r1, c1, r2, c2, v]
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class SubrectangleQueries {
  public SubrectangleQueries(int[][] rectangle) {
    this.rectangle = rectangle;
  }

  public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
    updates.add(new int[] {row1, col1, row2, col2, newValue});
  }

  public int getValue(int row, int col) {
    for (int i = updates.size() - 1; i >= 0; --i) {
      int[] update = updates.get(i);
      final int r1 = update[0];
      final int c1 = update[1];
      final int r2 = update[2];
      final int c2 = update[3];
      final int v = update[4];
      if (r1 <= row && row <= r2 && c1 <= col && col <= c2)
        return v;
    }
    return rectangle[row][col];
  }

  private int[][] rectangle;
  private List<int[]> updates = new ArrayList<>(); // [r1, c1, r2, c2, v]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class SubrectangleQueries:
  def __init__(self, rectangle: list[list[int]]):
    self.rectangle = rectangle
    self.updates = []

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

  def getValue(self, row: int, col: int) -> int:
    for r1, c1, r2, c2, v in reversed(self.updates):
      if r1 <= row <= r2 and c1 <= col <= c2:
        return v
    return self.rectangle[row][col]