024.md

1476. Subrectangle Queries

Difficulty: 🟡 Medium

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.

Examples:

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 (4x3) 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

Solutions

O((row2 - row1 + 1) * (col2 - col1 + 1)) solution in Python3

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 row in range(row1, row2+1):
            for col in range(col1, col2+1):
                self._rectangle[row][col] = newValue

    def getValue(self, row: int, col: int) -> int:
        return self._rectangle[row][col]


# Your SubrectangleQueries object will be instantiated and called as such:
# obj = SubrectangleQueries(rectangle)
# obj.updateSubrectangle(row1,col1,row2,col2,newValue)
# param_2 = obj.getValue(row,col)

The SubrectangleQueries class maintains a rectangle as a 2D matrix of integers. The constructor initializes the rectangle with the given matrix. The class supports two methods: updateSubrectangle and getValue.

1. updateSubrectangle:

   • This method takes the coordinates (row1, col1) and (row2, col2) of the subrectangle and the newValue.
   • It iterates through each cell within the specified subrectangle and updates its value to newValue.
   • This operation has a time complexity of O((row2 - row1 + 1) * (col2 - col1 + 1)).

2. getValue:

   • This method takes the coordinates (row, col) and returns the current value of the cell in the rectangle at the specified coordinates.
   • This operation has a time complexity of O(1).

Analysis of Time and Space Complexity

The time complexity of the updateSubrectangle method is O((row2 - row1 + 1) * (col2 - col1 + 1)) as it iterates through each cell within the specified subrectangle.

The time complexity of the getValue method is O(1) as it directly accesses the value at the specified coordinates in the rectangle.

The space complexity of the SubrectangleQueries class is O(rows * cols) as it stores the rectangle as a 2D matrix.

Summary

The SubrectangleQueries class provides methods to update and retrieve values from a rectangle represented as a 2D matrix of integers. The updateSubrectangle method updates all values within a specified subrectangle, and the getValue method retrieves the value at a specific coordinate. The class has a time complexity of O((row2 - row1 + 1) * (col2 - col1 + 1)) for updating values and O(1) for retrieving values. The space complexity is O(rows * cols).

NB: If you want to get community points please suggest solutions in other languages as merge requests.