Subrectangle Queries

MEDIUM

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.

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

Approaches

Checkout 2 different approaches to solve Subrectangle Queries. Click on different approaches to view the approach and algorithm in detail.

Brute-force Update

This approach involves directly modifying the underlying matrix for each update operation. The updateSubrectangle method iterates through all the cells in the specified subrectangle and changes their values. The getValue method simply retrieves the value from the stored matrix.

Algorithm

Initialize a 2D array rectangle in the constructor with the given input matrix.
For updateSubrectangle, use two nested loops to traverse the subrectangle from (row1, col1) to (row2, col2).
In the inner loop, set the value of the current cell rectangle[i][j] to newValue.
For getValue, directly access and return the value at rectangle[row][col].

In this approach, we store the rectangle as a 2D array. When an update is requested, we iterate over all the cells in the given subrectangle and set their value to the new value. When a value is requested, we simply return the value at the given coordinates from our stored 2D array.

Algorithm:

Constructor SubrectangleQueries(rectangle): Store the input rectangle in a member variable.
updateSubrectangle(row1, col1, row2, col2, newValue): Use nested loops to iterate from i = row1 to row2 and j = col1 to col2. In each iteration, set rectangle[i][j] = newValue.
getValue(row, col): Return rectangle[row][col].

Code Snippet:

class SubrectangleQueries {
    private int[][] rectangle;

    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;
    }

    public 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++) {
                this.rectangle[i][j] = newValue;
            }
        }
    }

    public int getValue(int row, int col) {
        return this.rectangle[row][col];
    }
}

Complexity Analysis

Time Complexity: `updateSubrectangle`: O(N * M), where N is `row2 - row1 + 1` and M is `col2 - col1 + 1`. In the worst case, this is O(rows * cols). `getValue`: O(1).Space Complexity: O(rows * cols) to store the matrix. This space is inherent to the problem statement.

Pros and Cons

Pros:

Simple to implement and understand.
The getValue operation is very fast (constant time).

Cons:

The updateSubrectangle operation can be slow for large subrectangles, making it inefficient if updates are frequent or cover large areas.

Code Solutions

Checking out 3 solutions in different languages for Subrectangle Queries. Click on different languages to view the code.

class SubrectangleQueries { private int [][] g ; private LinkedList < int []> ops = new LinkedList <>(); public SubrectangleQueries ( int [][] rectangle ) { g = rectangle ; } public void updateSubrectangle ( int row1 , int col1 , int row2 , int col2 , int newValue ) { ops . addFirst ( new int [] { row1 , col1 , row2 , col2 , newValue }); } public int getValue ( int row , int col ) { for ( var op : ops ) { if ( op [ 0 ] <= row && row <= op [ 2 ] && op [ 1 ] <= col && col <= op [ 3 ]) { return op [ 4 ]; } } return g [ 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); */

Video Solution

Watch the video walkthrough for Subrectangle Queries

Patterns:

Design

Data Structures:

ArrayMatrix

Companies:

Info Edge |Nuro |