1476. Subrectangle Queries - Solution

Q: Is Subrectangle Queries easy or hard?

Subrectangle Queries is classified as a Medium problem because it tests data structure design rather than algorithmic complexity. The logic is straightforward once you recognize that brute-force rectangle updates are acceptable within the constraints.

Q: Subrectangle Queries Python/Java solution

Python and Java implementations usually store the original matrix inside a class and expose two methods: updateSubrectangle and getValue. The update method loops through the specified rectangle and assigns the new value, while getValue simply returns matrix[row][col]. This keeps the implementation concise and efficient.

Q: How to solve Subrectangle Queries in O(n)?

The problem can be handled efficiently by iterating through the cells of the target rectangle during each update. This results in O(area) time for updates and O(1) for queries. Another design stores updates as overlays and resolves the value during queries by scanning recent updates first, which keeps updates O(1).

Q: What is the best approach for Subrectangle Queries?

The direct matrix update approach is typically the best for this problem. Each update iterates through the affected rectangle and writes the new value directly into the matrix, giving O(1) query time. Given the small constraints in the problem, this approach is simple and efficient. A lazy overlay design is an alternative if you want constant-time updates and can tolerate slower queries.

Q: Is Subrectangle Queries asked at Google/Amazon/Meta?

Problems involving matrix updates and custom data structure design appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear verbatim, similar questions about efficient range updates and query operations are common in system design and data structure rounds.

Q: What data structure is used in Subrectangle Queries?

The core data structure is a 2D matrix backed by arrays. The direct solution modifies the matrix directly, while the alternative design stores update rectangles in a list as overlay operations. Both approaches rely on array indexing and coordinate range checks.

Q: What is the time complexity of Subrectangle Queries?

In the direct update approach, updating a rectangle takes O((r2-r1+1)*(c2-c1+1)) time while getValue runs in O(1). With the lazy overlay method, update operations are O(1) because updates are stored rather than applied, while getValue may take O(k) time where k is the number of updates checked.

The 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.

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

Approach overview

Problem Overview: You need to design a data structure that stores a matrix and supports two operations: update all values inside a subrectangle and return the value of a specific cell. The challenge is balancing update cost with query performance.

Approach 1: Direct Matrix Update (Update: O((r2-r1+1)*(c2-c1+1)), Query: O(1), Space: O(1))

Store the matrix directly and modify it during every update operation. When updateSubrectangle(row1, col1, row2, col2, newValue) is called, iterate through all rows from row1 to row2 and all columns from col1 to col2, assigning newValue to each cell. The getValue(row, col) operation becomes a constant-time lookup because the matrix always reflects the latest state. This approach is simple and predictable, and it performs well when the number of update operations is small or when rectangles are relatively small.

This method relies only on basic iteration over a matrix and fits naturally with typical array manipulation patterns. The tradeoff is that large rectangle updates can be expensive because every affected cell must be modified immediately.

Approach 2: Lazy Update With Overlays (Update: O(1), Query: O(k), Space: O(k))

Instead of modifying the matrix immediately, store each update as an overlay record containing (row1, col1, row2, col2, value). The base matrix remains unchanged. Each update simply appends a new record to a list, making the update operation constant time.

When getValue(row, col) is called, iterate through the updates in reverse order (most recent first). Check whether the queried cell lies inside any stored rectangle. The first matching update determines the value. If no update covers the cell, return the original matrix value. This technique shifts the cost from updates to queries and demonstrates a common design pattern where writes are cheap and reads resolve the final state lazily.

This approach is efficient when updates are frequent but queries are relatively limited. Because updates are stored rather than applied, memory grows with the number of updates.

Recommended for interviews: The direct matrix update approach is usually the expected solution because it keeps the implementation straightforward and meets the problem constraints. Mentioning the lazy overlay strategy shows deeper system design thinking. It demonstrates that you can trade immediate computation for deferred resolution, which is a common optimization pattern in data structure design.

Approach 1: Direct Matrix Update

This approach involves directly modifying the original matrix whenever an update is requested. Each cell in the specified subrectangle is updated with the new value. The getValue function simply retrieves the desired cell value using its coordinates, as the matrix is up-to-date after each operation.

Python

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

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

Java

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

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

C++

#include <vector>
using namespace std;

class SubrectangleQueries {
public:
    vector<vector<int>> rectangle;

    SubrectangleQueries(vector<vector<int>>& rectangle) {
        this->rectangle = 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) {
                rectangle[i][j] = newValue;
            }
        }
    }

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

JavaScript

class SubrectangleQueries {
    constructor(rectangle) {
        this.rectangle = rectangle;
    }

    updateSubrectangle(row1, col1, row2, col2, newValue) {
        for (let i = row1; i <= row2; i++) {
            for (let j = col1; j <= col2; j++) {
                this.rectangle[i][j] = newValue;
            }
        }
    }

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

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int** rectangle;
    int rows;
    int cols;
} SubrectangleQueries;

SubrectangleQueries* subrectangleQueriesCreate(int** rectangle, int rows, int cols) {
    SubrectangleQueries* obj = (SubrectangleQueries*) malloc(sizeof(SubrectangleQueries));
    obj->rectangle = rectangle;
    obj->rows = rows;
    obj->cols = cols;
    return obj;
}

void subrectangleQueriesUpdateSubrectangle(SubrectangleQueries* obj, int row1, int col1, int row2, int col2, int newValue) {
    for (int i = row1; i <= row2; i++) {
        for (int j = col1; j <= col2; j++) {
            obj->rectangle[i][j] = newValue;
        }
    }
}

int subrectangleQueriesGetValue(SubrectangleQueries* obj, int row, int col) {
    return obj->rectangle[row][col];
}

void subrectangleQueriesFree(SubrectangleQueries* obj) {
    free(obj);
}

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

    public int GetValue(int row, int col) {
        return rectangle[row][col];
    }
}

Python's straightforward approach leverages list comprehension to update subrectangle values directly. getValue simply returns the value at the specified coordinates in the matrix.

Complexity

The update operation takes O(m * n) time, where m and n are the subrectangle's dimensions. Value retrieval operates in O(1) time. The space complexity is O(1).

Try this approach in the editor

Approach 2: Lazy Update With Overlays

This approach optimizes by recording updates instead of applying them directly to the matrix until getValue is called. Each update stores information about the subrectangle and new value to apply. When retrieving a value, it checks the latest applicable update and applies overlays if needed, optimizing space and computational efficiency for a large number of updates.

Python

class SubrectangleQueries:
    def __init__(self, rectangle: List[List[int]]):
        self.rectangle = rectangle
        self.updates = []

    def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
        self.updates.append((row1, col1, row2, col2, newValue))

    def getValue(self, row: int, col: int) -> int:
        for row1, col1, row2, col2, newValue in reversed(self.updates):
            if row1 <= row <= row2 and col1 <= col <= col2:
                return newValue
        return self.rectangle[row][col]

Java

import java.util.ArrayList;
import java.util.List;

class SubrectangleQueries {
    private int[][] rectangle;
    private List<int[]> updates;

    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;
        this.updates = new ArrayList<>();
    }

    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        updates.add(new int[]{row1, col1, row2, col2, newValue});
    }

    public int getValue(int row, int col) {
        for (int i = updates.size() - 1; i >= 0; --i) {
            int[] update = updates.get(i);
            if (update[0] <= row && row <= update[2] && update[1] <= col && col <= update[3]) {
                return update[4];
            }
        }
        return rectangle[row][col];
    }
}

C++

#include <vector>
using namespace std;

class SubrectangleQueries {
    vector<vector<int>> rectangle;
    vector<vector<int>> memory;
public:
    SubrectangleQueries(vector<vector<int>>& rectangle) : rectangle(rectangle) {}

    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        memory.push_back({row1, col1, row2, col2, newValue});
    }

    int getValue(int row, int col) {
        for (auto it = memory.rbegin(); it != memory.rend(); ++it) {
            if ((*it)[0] <= row && row <= (*it)[2] && (*it)[1] <= col && col <= (*it)[3]) {
                return (*it)[4];
            }
        }
        return rectangle[row][col];
    }
};

JavaScript

class SubrectangleQueries {
    constructor(rectangle) {
        this.rectangle = rectangle;
        this.updates = [];
    }

    updateSubrectangle(row1, col1, row2, col2, newValue) {
        this.updates.push([row1, col1, row2, col2, newValue]);
    }

    getValue(row, col) {
        for (let i = this.updates.length - 1; i >= 0; i--) {
            const [row1, col1, row2, col2, newValue] = this.updates[i];
            if (row1 <= row && row <= row2 && col1 <= col && col <= col2) {
                return newValue;
            }
        }
        return this.rectangle[row][col];
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int row1, col1, row2, col2, newValue;
} Update;

typedef struct {
    int** rectangle;
    int updateCount;
    Update* updates[500];
    int rows, cols;
} SubrectangleQueries;

SubrectangleQueries* subrectangleQueriesCreate(int** rectangle, int rows, int cols) {
    SubrectangleQueries* obj = (SubrectangleQueries*) malloc(sizeof(SubrectangleQueries));
    obj->rectangle = rectangle;
    obj->updateCount = 0;
    obj->rows = rows;
    obj->cols = cols;
    return obj;
}

void subrectangleQueriesUpdateSubrectangle(SubrectangleQueries* obj, int row1, int col1, int row2, int col2, int newValue) {
    Update* update = (Update*) malloc(sizeof(Update));
    update->row1 = row1;
    update->col1 = col1;
    update->row2 = row2;
    update->col2 = col2;
    update->newValue = newValue;
    obj->updates[obj->updateCount++] = update;
}

int subrectangleQueriesGetValue(SubrectangleQueries* obj, int row, int col) {
    for (int i = obj->updateCount - 1; i >= 0; i--) {
        Update* update = obj->updates[i];
        if (row >= update->row1 && row <= update->row2 && col >= update->col1 && col <= update->col2) {
            return update->newValue;
        }
    }
    return obj->rectangle[row][col];
}

void subrectangleQueriesFree(SubrectangleQueries* obj) {
    for (int i = 0; i < obj->updateCount; i++) {
        free(obj->updates[i]);
    }
    free(obj);
}

using System;
using System.Collections.Generic;

public class SubrectangleQueries {
    private int[][] rectangle;
    private List<int[]> updates;

    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;
        this.updates = new List<int[]>();
    }

    public void UpdateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        updates.Add(new[] { row1, col1, row2, col2, newValue });
    }

    public int GetValue(int row, int col) {
        for (int i = updates.Count - 1; i >= 0; --i) {
            var update = updates[i];
            if (update[0] <= row && row <= update[2] && update[1] <= col && col <= update[3]) {
                return update[4];
            }
        }
        return rectangle[row][col];
    }
}

Python's implementation maintains a list of updates and checks backwards to evaluate the most recent application. This enables efficient retrieval, especially when a high number of updates occur between accesses.

Complexity

The update function operates in O(1) time, and accessing a cell operates in O(U) time, with space requirements of O(U).

Try this approach in the editor

Approach 3: Default Approach

TypeScript

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

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);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Direct Matrix Update	The update operation takes O(m * n) time, where m and n are the subrectangle's dimensions. Value retrieval operates in O(1) time. The space complexity is O(1).
Lazy Update With Overlays	The update function operates in O(1) time, and accessing a cell operates in O(U) time, with space requirements of O(U).
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Direct Matrix Update	Update: O((r2-r1+1)*(c2-c1+1)), Query: O(1)	O(1)	Best when updates are limited or rectangles are small and constant-time queries are required
Lazy Update With Overlays	Update: O(1), Query: O(k)	O(k)	Useful when updates are frequent and you want to avoid repeatedly modifying large subrectangles

Frequently asked questions

Is Subrectangle Queries easy or hard?

Subrectangle Queries is classified as a Medium problem because it tests data structure design rather than algorithmic complexity. The logic is straightforward once you recognize that brute-force rectangle updates are acceptable within the constraints.

Subrectangle Queries Python/Java solution

Python and Java implementations usually store the original matrix inside a class and expose two methods: updateSubrectangle and getValue. The update method loops through the specified rectangle and assigns the new value, while getValue simply returns matrix[row][col]. This keeps the implementation concise and efficient.

How to solve Subrectangle Queries in O(n)?

The problem can be handled efficiently by iterating through the cells of the target rectangle during each update. This results in O(area) time for updates and O(1) for queries. Another design stores updates as overlays and resolves the value during queries by scanning recent updates first, which keeps updates O(1).

What is the best approach for Subrectangle Queries?

The direct matrix update approach is typically the best for this problem. Each update iterates through the affected rectangle and writes the new value directly into the matrix, giving O(1) query time. Given the small constraints in the problem, this approach is simple and efficient. A lazy overlay design is an alternative if you want constant-time updates and can tolerate slower queries.

Is Subrectangle Queries asked at Google/Amazon/Meta?

Problems involving matrix updates and custom data structure design appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear verbatim, similar questions about efficient range updates and query operations are common in system design and data structure rounds.

What data structure is used in Subrectangle Queries?

The core data structure is a 2D matrix backed by arrays. The direct solution modifies the matrix directly, while the alternative design stores update rectangles in a list as overlay operations. Both approaches rely on array indexing and coordinate range checks.

What is the time complexity of Subrectangle Queries?

In the direct update approach, updating a rectangle takes O((r2-r1+1)*(c2-c1+1)) time while getValue runs in O(1). With the lazy overlay method, update operations are O(1) because updates are stored rather than applied, while getValue may take O(k) time where k is the number of updates checked.

Subrectangle Queries solution and explanation

The problem

Approach overview

Approach 1: Direct Matrix Update

Approach 2: Lazy Update With Overlays

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Subrectangle Queries solution and explanation

The problem

Approach overview

Approach 1: Direct Matrix Update

Approach 2: Lazy Update With Overlays

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems