We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Subrectangle Queries

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires efficient updates and queries on a 2D matrix.
  • Directly updating all elements in the specified subrectangle can be inefficient for large updates.
  • Maintaining a simple 2D array can simplify the implementation for both methods.

Space and Time Complexity

Time Complexity:

  • updateSubrectangle: O((row2 - row1 + 1) * (col2 - col1 + 1)) for updating the values.
  • getValue: O(1) for retrieving a value.

Space Complexity: O(rows * cols) for storing the rectangle.

Solution

The solution utilizes a 2D array to represent the rectangle. The updateSubrectangle method iterates through the specified subrectangle and updates each element to the new value. The getValue method directly accesses the value at the given coordinates. This straightforward approach is feasible given the constraints.

Code Solutions

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

    def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
        for i in range(row1, row2 + 1):
            for j in range(col1, col2 + 1):
                self.rectangle[i][j] = newValue

    def getValue(self, row: int, col: int) -> int:
        return self.rectangle[row][col]
← Back to All Questions