Subrectangle Queries - Practice Coding Problems

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.

Input & Output

Example 1 — Basic Operations

$ Input: [["SubrectangleQueries",[[1,2,1],[4,3,4],[3,2,1]]],["getValue",[0,2]],["updateSubrectangle",[0,0,2,2,5]],["getValue",[0,2]],["getValue",[2,1]]]

› Output: [null,1,null,5,5]

💡 Note: Initialize with matrix [[1,2,1],[4,3,4],[3,2,1]], getValue(0,2) returns 1, update subrectangle to 5, getValue(0,2) now returns 5, getValue(2,1) returns 5

Example 2 — Multiple Updates

$ Input: [["SubrectangleQueries",[[1,1,1],[2,2,2],[3,3,3]]],["updateSubrectangle",[0,0,1,1,10]],["getValue",[0,0]],["updateSubrectangle",[1,1,2,2,20]],["getValue",[1,1]]]

› Output: [null,null,10,null,20]

💡 Note: First update sets top-left 2x2 to 10, second update overlaps and sets bottom-right 2x2 to 20

Example 3 — Edge Case Single Cell

$ Input: [["SubrectangleQueries",[[5]]],["getValue",[0,0]],["updateSubrectangle",[0,0,0,0,3]],["getValue",[0,0]]]

› Output: [null,5,null,3]

💡 Note: Single cell matrix, getValue returns 5, update single cell to 3, getValue returns 3

Constraints

1 ≤ rows, cols ≤ 100
0 ≤ row1 ≤ row2 < rows
0 ≤ col1 ≤ col2 < cols
1 ≤ newValue, rectangle[i][j] ≤ 10⁹
At most 500 calls to updateSubrectangle and getValue

Visualization

Tap to expand

Understanding the Visualization

Initialize

Create matrix with given values

Update

Modify rectangular region with new value

Query

Retrieve value at specific position

Key Takeaway

🎯 Key Insight: Choose between direct matrix updates (simple) or update history tracking (efficient for frequent updates)

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is that we can either update the matrix directly (simple but slow for large updates) or store update history and check recent updates first (faster for frequent updates). Best approach depends on the update/query ratio. Update history tracking is optimal when updates are frequent: Time: O(U) per query, Space: O(R×C + U).

Common Approaches

Approach	Time	Space	Notes
✓ Direct Matrix Updates	O(R×C)	O(R×C)	Directly update all cells in the subrectangle for each update operation
Update History Tracking	O(U)	O(R×C + U)	Store update operations and check recent updates during getValue

Direct Matrix Updates — Algorithm Steps

Initialize matrix with given rectangle
For updateSubrectangle: iterate through all cells in range and set to newValue
For getValue: return matrix[row][col]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create matrix with original values

Update

Set all cells in subrectangle to new value

Query

Return value at specific position

Code -

solution.c — C

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

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

SubrectangleQueries* subrectangleQueriesCreate(int** rectangle, int rectangleSize, int* rectangleColSize) {
    SubrectangleQueries* obj = (SubrectangleQueries*)malloc(sizeof(SubrectangleQueries));
    obj->rows = rectangleSize;
    obj->cols = rectangleColSize[0];
    obj->matrix = (int**)malloc(obj->rows * sizeof(int*));
    
    for (int i = 0; i < obj->rows; i++) {
        obj->matrix[i] = (int*)malloc(obj->cols * sizeof(int));
        for (int j = 0; j < obj->cols; j++) {
            obj->matrix[i][j] = rectangle[i][j];
        }
    }
    
    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->matrix[i][j] = newValue;
        }
    }
}

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

int main() {
    printf("[null,null,1,null,1,1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(R×C)

Each update operation requires iterating through at most R×C cells in the subrectangle

✓ Linear Growth

Space Complexity

O(R×C)

Store the original matrix of size R×C

✓ Linear Space

25.3K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Matrix Updates — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler