Subrectangle Queries - Solution & Explanation

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.

MediumArray Design Matrix16 min readAsked at: Google, Info Edge, Nuro

Practice this problem

Problem Statement

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.

The C solution defines a struct containing a pointer to the rectangle, along with its dimensions. The updateSubrectangle function iterates over the specified subrectangle, updating each value to newValue. The getValue function directly accesses the value at the given coordinates.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

The time complexity for updateSubrectangle is O((row2-row1+1) * (col2-col1+1)), or O(m * n) in the worst case. getValue runs in O(1) time. The space complexity is O(1), excluding the input matrix size.

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.

The lazy update structure in C uses an array of updates, capturing the operations rather than directly modifying the matrix. It iterates through updates in reverse to check applicability when retrieving a value, allowing efficient accesses without unnecessary updates.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time complexity of updateSubrectangle is O(1), while getValue has O(U) complexity, where U is the count of updates. Space complexity is O(U).

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Direct Matrix Update	The time complexity for `updateSubrectangle` is O((row2-row1+1) * (col2-col1+1)), or O(m * n) in the worst case. `getValue` runs in O(1) time. The space complexity is O(1), excluding the input matrix size.
Lazy Update With Overlays	Time complexity of `updateSubrectangle` is O(1), while `getValue` has O(U) complexity, where U is the count of updates. Space complexity is O(U).
Default Approach	—

Detailed 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

Video Solution

LeetCode 1476. Subrectangle Queries Solution Explained - Java • Algorithms and Data Structures Course • 1,981 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Subrectangle Queries with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance86.3%

Approaches3

Reading time16 min

Asked at

Google Info Edge Nuro

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Direct Matrix Update

Code

Complexity

Approach 2: Lazy Update With Overlays

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents