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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subrectangle Queries

Number: 1572

Difficulty: Medium

Paid? No

Companies: Google, Nuro

Problem Description

Design a class SubrectangleQueries that initializes with a 2D grid (rectangle) of integers and supports two operations: updateSubrectangle and getValue. The updateSubrectangle method updates all elements within a given subrectangle to a specified new value, and the getValue method retrieves the current value at a given coordinate in the rectangle.

Key Insights

  • The rectangle is stored internally as a 2D list (or array).
  • The updateSubrectangle method performs a nested loop over the specified rows and columns to update values.
  • Each operation is straightforward given the constraints.
  • Considering the constraints (rows, cols up to 100 and maximum 500 operations), iterating over the subrectangle is efficient enough.

Space and Time Complexity

Time Complexity:

  • updateSubrectangle: O(m*n) in the worst case (where m and n are the dimensions of the subrectangle being updated).
  • getValue: O(1).

Space Complexity: O(R * C) where R and C are the dimensions of the rectangle.

Solution

The solution leverages a simple 2D array to store the rectangle. The updateSubrectangle method uses two nested loops to iterate over the specified subrectangle boundaries and sets each element to the new value. The getValue method simply returns the element at the requested row and column. This approach is optimal given the problem constraints and directly addresses the required operations without unnecessary complexity.

Code Solutions

# Python implementation of SubrectangleQueries
class SubrectangleQueries:
    def __init__(self, rectangle):
        # Store the initial rectangle
        self.rectangle = rectangle

    def updateSubrectangle(self, row1, col1, row2, col2, newValue):
        # Loop through each row in the specified subrectangle
        for row in range(row1, row2 + 1):
            # Loop through each column in the specified subrectangle
            for col in range(col1, col2 + 1):
                self.rectangle[row][col] = newValue

    def getValue(self, row, col):
        # Return the value at a particular coordinate
        return self.rectangle[row][col]

# Example usage:
# obj = SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]])
# print(obj.getValue(0, 2))
# obj.updateSubrectangle(0, 0, 3, 2, 5)
# print(obj.getValue(0, 2))
← Back to All Questions