Subrectangle Queries

Problem

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


**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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


**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

Solution

Method 1 - Brute Force (Direct Update)

Intuition

Since the number of operations is small (≤ 500) and the matrix is small (≤ 100x100), we can directly update the matrix for each update and return the value for each query.

Approach

Store the matrix as a 2D array.
For updateSubrectangle, iterate over the specified subrectangle and set each value to newValue.
For getValue, return the value at the specified cell.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


#include <vector>
using namespace std;
class SubrectangleQueries {
    vector<vector<int>> rect;
public:
    SubrectangleQueries(vector<vector<int>>& rectangle) : rect(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)
                rect[i][j] = newValue;
    }
    int getValue(int row, int col) {
        return rect[row][col];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


type SubrectangleQueries struct {
    rect [][]int
}
func Constructor(rectangle [][]int) SubrectangleQueries {
    r := make([][]int, len(rectangle))
    for i := range rectangle {
        r[i] = append([]int{}, rectangle[i]...)
    }
    return SubrectangleQueries{r}
}
func (this *SubrectangleQueries) UpdateSubrectangle(row1, col1, row2, col2, newValue int) {
    for i := row1; i <= row2; i++ {
        for j := col1; j <= col2; j++ {
            this.rect[i][j] = newValue
        }
    }
}
func (this *SubrectangleQueries) GetValue(row, col int) int {
    return this.rect[row][col]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class SubrectangleQueries {
    private int[][] rect;
    public SubrectangleQueries(int[][] rectangle) {
        rect = new int[rectangle.length][rectangle[0].length];
        for (int i = 0; i < rectangle.length; ++i)
            rect[i] = rectangle[i].clone();
    }
    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)
                rect[i][j] = newValue;
    }
    public int getValue(int row, int col) {
        return rect[row][col];
    }
}

1
2
3
4
5
6
7
8
9


class SubrectangleQueries(rectangle: Array<IntArray>) {
    private val rect = Array(rectangle.size) { rectangle[it].clone() }
    fun updateSubrectangle(row1: Int, col1: Int, row2: Int, col2: Int, newValue: Int) {
        for (i in row1..row2)
            for (j in col1..col2)
                rect[i][j] = newValue
    }
    fun getValue(row: Int, col: Int): Int = rect[row][col]
}

1
2
3
4
5
6
7
8
9


class SubrectangleQueries:
    def __init__(self, rectangle):
        self.rect = [row[:] for row in rectangle]
    def updateSubrectangle(self, row1, col1, row2, col2, newValue):
        for i in range(row1, row2+1):
            for j in range(col1, col2+1):
                self.rect[i][j] = newValue
    def getValue(self, row, col):
        return self.rect[row][col]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


pub struct SubrectangleQueries {
    rect: Vec<Vec<i32>>,
}
impl SubrectangleQueries {
    pub fn new(rectangle: Vec<Vec<i32>>) -> Self {
        Self { rect: rectangle }
    }
    pub fn update_subrectangle(&mut self, row1: i32, col1: i32, row2: i32, col2: i32, new_value: i32) {
        for i in row1..=row2 {
            for j in col1..=col2 {
                self.rect[i as usize][j as usize] = new_value;
            }
        }
    }
    pub fn get_value(&self, row: i32, col: i32) -> i32 {
        self.rect[row as usize][col as usize]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class SubrectangleQueries {
    private rect: number[][];
    constructor(rectangle: number[][]) {
        this.rect = rectangle.map(row => row.slice());
    }
    updateSubrectangle(row1: number, col1: number, row2: number, col2: number, newValue: number): void {
        for (let i = row1; i <= row2; i++)
            for (let j = col1; j <= col2; j++)
                this.rect[i][j] = newValue;
    }
    getValue(row: number, col: number): number {
        return this.rect[row][col];
    }
}

Complexity

⏰ Time complexity: O(R*C) per update, O(1) per query
🧺 Space complexity: O(R*C)

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 - Brute Force (Direct Update)#

Intuition#

Approach#

Code#

Complexity#