1476. Subrectangle Queries LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1476. Subrectangle Queries LeetCode Solution with the best time and space complexity. The solution to Subrectangle Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Subrectangle Queries solution in C++
Subrectangle Queries solution in Java
Subrectangle Queries solution in Python
Additional Resources

1476. Subrectangle Queries LeetCode Solution image

Problem Statement of Subrectangle Queries

Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:
1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

Updates all values with newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).

2. getValue(int row, int col)

Returns the current value of the coordinate (row,col) from the rectangle.

Example 1:

Input
[“SubrectangleQueries”,”getValue”,”updateSubrectangle”,”getValue”,”getValue”,”updateSubrectangle”,”getValue”,”getValue”]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
Output
[null,1,null,5,5,null,10,5]
Explanation
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);
// The initial rectangle (4×3) looks like:
// 1 2 1
// 4 3 4
// 3 2 1
// 1 1 1
subrectangleQueries.getValue(0, 2); // return 1
subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);
// After this update the rectangle looks like:
// 5 5 5
// 5 5 5
// 5 5 5
// 5 5 5
subrectangleQueries.getValue(0, 2); // return 5
subrectangleQueries.getValue(3, 1); // return 5
subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// After this update the rectangle looks like:
// 5 5 5
// 5 5 5
// 5 5 5
// 10 10 10
subrectangleQueries.getValue(3, 1); // return 10
subrectangleQueries.getValue(0, 2); // return 5

Example 2:

Input
[“SubrectangleQueries”,”getValue”,”updateSubrectangle”,”getValue”,”getValue”,”updateSubrectangle”,”getValue”]
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
Output
[null,1,null,100,100,null,20]
Explanation
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);
subrectangleQueries.getValue(0, 0); // return 1
subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);
subrectangleQueries.getValue(0, 0); // return 100
subrectangleQueries.getValue(2, 2); // return 100
subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);
subrectangleQueries.getValue(2, 2); // return 20

Constraints:

There will be at most 500 operations considering both methods: updateSubrectangle and getValue.
1 <= rows, cols <= 100
rows == rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols

Complexity Analysis

Time Complexity: O(|\texttt{updateSubrectangle()}|)
Space Complexity: O(|\texttt{updateSubrectangle()}|)

1476. Subrectangle Queries LeetCode Solution in C++

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]
};
/* code provided by PROGIEZ */

1476. Subrectangle Queries LeetCode Solution in Java

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]
}
// code provided by PROGIEZ

1476. Subrectangle Queries LeetCode Solution in Python

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]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents