Leetcode 1476: Subrectangle Queries
You are tasked with implementing the SubrectangleQueries class which operates on a matrix representing a rectangle with integer values. The class should support two key operations: updateSubrectangle and getValue.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of method calls on the SubrectangleQueries object, where each call represents an operation to be performed.
Example: [[[1,2,3],[4,5,6],[7,8,9]]],[0,1],[1,1,2,2,10],[0,1],[1,2],[0,0,1,1,20],[1,0],[0,2]
Constraints:
• 1 <= rows, cols <= 100
• 0 <= row1 <= row2 < rows
• 0 <= col1 <= col2 < cols
• 1 <= newValue <= 10^9
• 0 <= row < rows
• 0 <= col < cols
Output: The output consists of the results of the method calls on the SubrectangleQueries object.
Example: [null,2,null,10,6,null,20,3]
Constraints:
• There will be at most 500 operations considering both methods.
Goal: The goal is to efficiently update a subrectangle and retrieve values at specified coordinates.
Steps:
• Store the initial matrix in the class.
• For the updateSubrectangle operation, iterate over the specified subrectangle and update all its values.
• For the getValue operation, simply retrieve the value from the matrix at the specified coordinates.
Goal: Constraints for the rectangle dimensions and operation limits.
Steps:
• 1 <= rows, cols <= 100
• 0 <= row1 <= row2 < rows
• 0 <= col1 <= col2 < cols
• 1 <= newValue, rectangle[i][j] <= 10^9
• 0 <= row < rows
• 0 <= col < cols
Assumptions:
• The rectangle is initially provided in the form of a 2D array.
• All values within the specified subrectangle are updated to the newValue.
• Input: [[[1,2,3],[4,5,6],[7,8,9]]],[0,1],[1,1,2,2,10],[0,1],[1,2],[0,0,1,1,20],[1,0],[0,2]
• Explanation: The provided example demonstrates how updates are made to specific subrectangles and how values are retrieved after those updates.
Approach: The problem can be solved with a straightforward approach that updates values directly in the matrix for the subrectangle and retrieves values using array indexing for the getValue operation.
Observations:
• The subrectangle update operation involves looping over a submatrix and updating values.
• The getValue operation is efficient with direct access to the matrix.
• Directly modifying the subrectangle will result in a time complexity of O(k), where k is the number of cells in the subrectangle.
Steps:
• Store the rectangle matrix in a 2D array.
• For updateSubrectangle, iterate through the subrectangle and set each element to the newValue.
• For getValue, simply return the value from the matrix at the given coordinates.
Empty Inputs:
• An empty rectangle is not a valid input.
Large Inputs:
• If the rectangle size is large, ensure the solution can handle large subrectangle updates efficiently.
Special Values:
• Handling the upper bound values for newValue and matrix elements should be done without overflow.
Constraints:
• Ensure that the row and column indices are within the valid bounds of the matrix.
vector<vector<int>> rec;
SubrectangleQueries(vector<vector<int>>& rectangle) {
rec = rectangle;
}
void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
for(int i = row1; i <= row2; i++)
for(int j = col1; j <= col2; j++)
rec[i][j] = newValue;
}
int getValue(int row, int col) {
return rec[row][col];
}
};
/**
* Your SubrectangleQueries object will be instantiated and called as such:
* SubrectangleQueries* obj = new SubrectangleQueries(rectangle);
* obj->updateSubrectangle(row1,col1,row2,col2,newValue);
* int param_2 = obj->getValue(row,col);
1 : Declaration
vector<vector<int>> rec;
This line declares a 2D vector `rec` that will hold the values of the subrectangle matrix. It is used to store the entire rectangle's data.
2 : Constructor
SubrectangleQueries(vector<vector<int>>& rectangle) {
The constructor initializes the `SubrectangleQueries` object with an existing 2D matrix `rectangle` passed by reference. This matrix is then stored in the `rec` variable.
3 : Initialization
rec = rectangle;
The matrix `rec` is initialized with the values from the provided `rectangle` matrix. This effectively stores the rectangle in the object for later updates and queries.
4 : Method
void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
The `updateSubrectangle` method is used to update the values of a subrectangle in the matrix. The rectangle to be updated is defined by the top-left (`row1`, `col1`) and bottom-right (`row2`, `col2`) corners, and the new value `newValue` is applied to all elements within this subrectangle.
5 : Loop
for(int i = row1; i <= row2; i++)
The outer loop iterates through all rows of the subrectangle, starting from `row1` to `row2`.
6 : Loop
for(int j = col1; j <= col2; j++)
The inner loop iterates through all columns of the subrectangle, starting from `col1` to `col2`.
7 : Update
rec[i][j] = newValue;
This line updates the value of each element in the subrectangle to the new value (`newValue`).
8 : Method
int getValue(int row, int col) {
The `getValue` method returns the value of the matrix at the specified position (`row`, `col`). This method allows querying individual values from the rectangle.
9 : Return
return rec[row][col];
This line retrieves the value from the matrix at the given position and returns it.
Best Case: O(1) for getValue
Average Case: O(k) for updateSubrectangle, where k is the size of the subrectangle
Worst Case: O(k) for updateSubrectangle
Description: The time complexity of getValue is constant, but updating the subrectangle requires iterating through the cells of the subrectangle.
Best Case: O(n * m)
Worst Case: O(n * m) where n is the number of rows and m is the number of columns in the rectangle.
Description: The space complexity depends on the size of the matrix, as we store it in memory.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus