Code Implementation

class SubrectangleQueries:
    def __init__(self, rectangle):
        self.rectangle = [row[:] for row in rectangle]
        self.updates = []

    def updateSubrectangle(self, row1, col1, row2, col2, newValue):
        self.updates.append((row1, col1, row2, col2, newValue))

    def getValue(self, row, col):
        for r1, c1, r2, c2, val in reversed(self.updates):
            if r1 <= row <= r2 and c1 <= col <= c2:
                return val
        return self.rectangle[row][col]
      

class SubrectangleQueries {
public:
    vector<vector<int>> rect;
    vector<tuple<int,int,int,int,int>> updates;
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        rect = rectangle;
    }
    
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        updates.push_back({row1, col1, row2, col2, newValue});
    }
    
    int getValue(int row, int col) {
        for (int i = updates.size()-1; i >= 0; --i) {
            auto [r1, c1, r2, c2, val] = updates[i];
            if (r1 <= row && row <= r2 && c1 <= col && col <= c2)
                return val;
        }
        return rect[row][col];
    }
};
      

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

    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = new int[rectangle.length][];
        for (int i = 0; i < rectangle.length; ++i)
            this.rectangle[i] = rectangle[i].clone();
        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[] u = updates.get(i);
            if (u[0] <= row && row <= u[2] && u[1] <= col && col <= u[3])
                return u[4];
        }
        return rectangle[row][col];
    }
}
      

var SubrectangleQueries = function(rectangle) {
    this.rectangle = rectangle.map(row => row.slice());
    this.updates = [];
};

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

SubrectangleQueries.prototype.getValue = function(row, col) {
    for (let i = this.updates.length - 1; i >= 0; --i) {
        let [r1, c1, r2, c2, val] = this.updates[i];
        if (r1 <= row && row <= r2 && c1 <= col && col <= c2)
            return val;
    }
    return this.rectangle[row][col];
};
      

Problem Description

The Subrectangle Queries problem involves designing a class to efficiently perform updates and queries on a 2D grid (rectangle) of integers.

You are given a 2D array called rectangle. The task is to implement a class with the following methods:

• updateSubrectangle(row1, col1, row2, col2, newValue): Updates all values in the subrectangle defined by its upper left corner (row1, col1) and bottom right corner (row2, col2) to newValue.
• getValue(row, col): Returns the current value at cell (row, col) in the rectangle.

• There will be multiple updateSubrectangle and getValue calls.
• Updates may overlap, and queries may occur before or after updates.
• There is always exactly one rectangle and all queries/updates are valid.

Thought Process

At first glance, it seems straightforward: for each updateSubrectangle call, simply iterate through all the relevant cells and set their value. However, if the rectangle is large and there are many updates, this approach becomes inefficient.

The challenge is to support both frequent updates and queries efficiently. The brute-force approach (updating every cell in the subrectangle each time) is slow. Instead, we can consider a more efficient way: record each update as an operation rather than applying it immediately.

When a getValue is called, we check if any updates affect the requested cell, starting from the most recent update. If so, return the value from the update; otherwise, return the original value from the rectangle.

This approach is efficient when the number of updates is much less than the number of cells in the rectangle, and it avoids unnecessary repeated writes.

Solution Approach

• Initialization: Store a copy of the original rectangle, so we always have access to the initial values.
• Storing Updates: Instead of updating all cells immediately, keep a list of updates. Each update is a tuple containing the affected subrectangle coordinates and the new value.
• Querying a Value: For getValue(row, col), iterate through the updates list in reverse order (from most recent to oldest). For each update, check if the cell (row, col) is inside the updated subrectangle. If found, return the update's value immediately. If none match, return the original value from the rectangle.

Why does this work? Because the most recent update that covers a cell determines its value. We only need to find the latest update that affects the cell, so we search updates in reverse.

Example Walkthrough

Suppose our initial rectangle is:
[[1,2,1],
[4,3,4],
[3,2,1],
[1,1,1]]

Step 1: updateSubrectangle(0, 0, 3, 2, 5)
All cells become 5. But we just record this update: (0,0,3,2,5).

Step 2: getValue(0, 2)
We check the updates in reverse (only one so far). The cell (0,2) is within (0,0)-(3,2), so we return 5.

Step 3: updateSubrectangle(3, 0, 3, 2, 10)
Now, the last row is updated to 10. We add this update: (3,0,3,2,10).

Step 4: getValue(3, 1)
We check updates in reverse. The latest update covers (3,1), so we return 10.

Step 5: getValue(0, 2)
The latest update only covers row 3, but (0,2) is not in row 3. The previous update covers (0,2), so we return 5.

Time and Space Complexity

• Brute-force Approach:
  • Update Time: O(R × C) per update (where R and C are the number of rows and columns in the subrectangle)
  • Query Time: O(1)
  • Space: O(M × N) for the rectangle
• Optimized Approach (current):
  • Update Time: O(1) per update (just appending to the updates list)
  • Query Time: O(U), where U is the number of updates (since we may need to check all updates in the worst case)
  • Space: O(M × N + U), for the rectangle and the updates list

The optimized approach is faster for updates and is efficient if the number of updates is much less than the number of cells. If there are many updates and queries, further optimizations may be possible.

Summary

The Subrectangle Queries problem demonstrates how to trade off between update and query efficiency by recording update operations instead of applying them immediately. This approach is particularly effective when updates are sparse relative to the size of the rectangle, allowing for quick updates and reasonable query times. The key insight is to always check the most recent relevant update for any cell, ensuring correctness and efficiency.