Subrectangle Queries - Leetcode Solution

Subrectangle Queries is a problem on LeetCode, which asks us to implement a class Rectangle which supports following operations on a 2D array:

1. Update the value of all cells in a rectangular area.
2. Query the value of a specified cell.

We need to implement the following class:

class SubrectangleQueries {
public:
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        
    }
    
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        
    }
    
    int getValue(int row, int col) {
        
    }
};

Approach

We can use a 2D array to store the rectangle and implement the given operations. For Update operation, we can iterate over the given rectangular area and update all the values. For Query operation, we can just return the value at the specified cell.

Implementation

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

    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];
    }
};

Complexity Analysis

• Time Complexity: Update operation takes O((row2 - row1 + 1) * (col2 - col1 + 1)) time as we need to update all cells in the given rectangular area. Query operation takes O(1) time as we just need to return the value at a cell.
• Space Complexity: O(m * n) where m and n are dimensions of the rectangle. We need to store all the values in the rectangle array.

1