Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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)
newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).2. getValue(int row, int col)
(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:
500 operations considering both methods: updateSubrectangle and getValue.1 <= rows, cols <= 100rows == rectangle.lengthcols == rectangle[i].length0 <= row1 <= row2 < rows0 <= col1 <= col2 < cols1 <= newValue, rectangle[i][j] <= 10^90 <= row < rows0 <= col < colsProblem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Design
["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]]
["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]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1476: Subrectangle Queries
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);
*/
// Accepted solution for LeetCode #1476: Subrectangle Queries
type SubrectangleQueries struct {
g [][]int
ops [][]int
}
func Constructor(rectangle [][]int) SubrectangleQueries {
return SubrectangleQueries{rectangle, [][]int{}}
}
func (this *SubrectangleQueries) UpdateSubrectangle(row1 int, col1 int, row2 int, col2 int, newValue int) {
this.ops = append(this.ops, []int{row1, col1, row2, col2, newValue})
}
func (this *SubrectangleQueries) GetValue(row int, col int) int {
for i := len(this.ops) - 1; i >= 0; i-- {
op := this.ops[i]
if op[0] <= row && row <= op[2] && op[1] <= col && col <= op[3] {
return op[4]
}
}
return this.g[row][col]
}
/**
* Your SubrectangleQueries object will be instantiated and called as such:
* obj := Constructor(rectangle);
* obj.UpdateSubrectangle(row1,col1,row2,col2,newValue);
* param_2 := obj.GetValue(row,col);
*/
# Accepted solution for LeetCode #1476: Subrectangle Queries
class SubrectangleQueries:
def __init__(self, rectangle: List[List[int]]):
self.g = rectangle
self.ops = []
def updateSubrectangle(
self, row1: int, col1: int, row2: int, col2: int, newValue: int
) -> None:
self.ops.append((row1, col1, row2, col2, newValue))
def getValue(self, row: int, col: int) -> int:
for r1, c1, r2, c2, v in self.ops[::-1]:
if r1 <= row <= r2 and c1 <= col <= c2:
return v
return self.g[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)
// Accepted solution for LeetCode #1476: Subrectangle Queries
struct SubrectangleQueries {
rectangle: Vec<Vec<i32>>,
n: usize,
m: usize,
}
impl SubrectangleQueries {
fn new(rectangle: Vec<Vec<i32>>) -> Self {
let n = rectangle.len();
let m = rectangle[0].len();
SubrectangleQueries { rectangle, n, m }
}
fn update_subrectangle(&mut self, row1: i32, col1: i32, row2: i32, col2: i32, new_value: i32) {
let r1 = row1 as usize;
let c1 = col1 as usize;
let r2 = row2 as usize;
let c2 = col2 as usize;
for i in r1..=r2 {
for j in c1..=c2 {
self.rectangle[i][j] = new_value;
}
}
}
fn get_value(&self, row: i32, col: i32) -> i32 {
self.rectangle[row as usize][col as usize]
}
}
#[test]
fn test() {
let rectangle = vec_vec_i32![[1, 2, 1], [4, 3, 4], [3, 2, 1], [1, 1, 1]];
let mut obj = SubrectangleQueries::new(rectangle);
assert_eq!(obj.get_value(0, 2), 1);
obj.update_subrectangle(0, 0, 3, 2, 5);
assert_eq!(obj.get_value(0, 2), 5);
}
// Accepted solution for LeetCode #1476: Subrectangle Queries
class SubrectangleQueries {
g: number[][];
ops: number[][];
constructor(rectangle: number[][]) {
this.g = rectangle;
this.ops = [];
}
updateSubrectangle(
row1: number,
col1: number,
row2: number,
col2: number,
newValue: number,
): void {
this.ops.push([row1, col1, row2, col2, newValue]);
}
getValue(row: number, col: number): number {
for (let i = this.ops.length - 1; ~i; --i) {
const [r1, c1, r2, c2, v] = this.ops[i];
if (r1 <= row && row <= r2 && c1 <= col && col <= c2) {
return v;
}
}
return this.g[row][col];
}
}
/**
* Your SubrectangleQueries object will be instantiated and called as such:
* var obj = new SubrectangleQueries(rectangle)
* obj.updateSubrectangle(row1,col1,row2,col2,newValue)
* var param_2 = obj.getValue(row,col)
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.