Skip to main content

Matrix

Subrectangle Queries Solution In C++/Python/java/JS

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.

Explanation

We have a matrix (a table of numbers) where each cell contains an integer. Our goal is to create a class that can:

  1. Update a subrectangle: Change all the values in a specified subrectangle (a smaller rectangle within the matrix) to a new value.
  2. Get the value of a cell: Retrieve the current value of any cell in the matrix.

Example

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

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
💡
Try Solving "Subrectangle Queries" Yourself First!
"The SubrectangleQueries" problem can be solved using different approaches, such as Brute Force and Optimal Iteration. Each approach has its advantages and trade-offs in terms of speed and memory usage.

Brute Force Approach

Intuition

The first thought that comes to our mind is to directly update the values in the specified subrectangle whenever an update operation is called. This approach is straightforward and easy to understand.

Imagine we have a matrix, and we want to change the values in a specific rectangular area within this matrix. The brute force approach involves iterating through each cell in the specified subrectangle and updating its value. This means we go row by row and column by column within the defined boundaries and set each cell to the new value.

For example, let's say we have the following matrix:

[[1, 2, 1], [4, 3, 4], [3, 2, 1], [1, 1, 1]]

If we want to update the subrectangle from (0,0) to (2,2) with the value 5, we start at the top-left corner (0,0) and move to the bottom-right corner (2,2), updating each cell along the way. After this update, the matrix looks like this:

[[5, 5, 5], [5, 5, 5], [5, 5, 5], [1, 1, 1]]

The approach is simple and ensures that all cells within the specified subrectangle are updated correctly and for the getValue(row, col) operation, we simply return matrix[row][col] because all updates are applied directly to the matrix during each update operation.

Find the Minimum Area to Cover All Ones I Algorithm

  1. We store the given matrix rectangle in an instance variable.
  2. We implement the updateSubrectangle method to update all values in the specified subrectangle.
  3. We iterate through each cell from (row1, col1) to (row2, col2) and set each cell to newValue.
  4. We implement the getValue method to retrieve the current value at the specified cell (row, col) in the matrix.

Approach

Initialize Variables: Store the given matrix rectangle in an instance variable.

Update Operation (updateSubrectangle):

    • Iterate through all rows from row1 to row2.
    • For each row, iterate through all columns from col1 to col2.
    • Update each cell rectangle[i][j] to newValue.

Retrieve Value (getValue): Directly return rectangle[row][col] from the matrix.

Return Final Value: The stored matrix always reflects the latest updates, ensuring direct access to the current value.

Dry-Run

General Setup:
Input: ["SubrectangleQueries", "getValue", "updateSubrectangle", "getValue", "getValue", "updateSubrectangle", "getValue"]
[[[[5, 6, 7], [8, 9, 10], [11, 12, 13]]], [1, 1], [0, 0, 2, 1, 50], [0, 1], [2, 1], [1, 0, 2, 2, 99], [2, 2]]
Output: [null, 9, null, 50, 50, null, 99]

Step-by-Step Execution:

Operation: getValue(1, 1)

  • Retrieve the value at row 1, column 1 → 9
  • Output: 9
  • No change in the rectangle.

Operation: updateSubrectangle(0, 0, 2, 1, 50)

  • Update all values from row 0 to 2 and column 0 to 1 to 50.
  • Updated Rectangle:
  • 50 50 7
  • 50 50 10
  • 50 50 13
  • Output: null (update operation does not return anything).

Operation: getValue(0, 1)

  • Retrieve value at row 0, column 1 → 50
  • Output: 50
  • No change in the rectangle.

Operation: getValue(2, 1)

  • Retrieve value at row 2, column 1 → 50
  • Output: 50
  • No change in the rectangle.

Operation: updateSubrectangle(1, 0, 2, 2, 99)

  • Update all values from row 1 to 2 and column 0 to 2 to 99.
  • Updated Rectangle:
  • 50 50 7
  • 99 99 99
  • 99 99 99
  • Output: null

Operation: getValue(2, 2)

  • Retrieve value at row 2, column 2 → 99
  • Output: 99
  • No change in the rectangle.

Final Output:

[null, 9, null, 50, 50, null, 99]

Subrectangle Queries solution

Let now discover the codes for Subrectangle Queries problem in C++, Java, Python, and JavaScript

Brute Force Code in all Languages.
1. Subrectangle Queries solution in C++ Try on Compiler 
class SubrectangleQueries {
    
    // 2D vector to store the rectangle values
    vector<vector<int>> rectangle;

public:

    // Constructor to initialize the rectangle
    SubrectangleQueries(vector<vector<int>>& rect) {
        rectangle = rect;
    }

    // Method to update a subrectangle with a new value
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        
        // Iterate through the rows within the specified range
        for (int i = row1; i <= row2; i++) {
            
            // Iterate through the columns within the specified range
            for (int j = col1; j <= col2; j++) {
                
                // Update the cell value to the new value
                rectangle[i][j] = newValue;
            }
        }
    }

    // Method to get the value at a specific position
    int getValue(int row, int col) {
        return rectangle[row][col];
    }
};

2. Subrectangle Queries solution in Java Try on Compiler 
class SubrectangleQueries {
    
    // 2D array to store the rectangle values
    int[][] rectangle;

    // Constructor to initialize the rectangle
    public SubrectangleQueries(int[][] rectangle) {
        this.rectangle = rectangle;
    }

    // Method to update a subrectangle with a new value
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        
        // Iterate through the rows within the specified range
        for (int i = row1; i <= row2; i++) {
            
            // Iterate through the columns within the specified range
            for (int j = col1; j <= col2; j++) {
                
                // Update the cell value to the new value
                this.rectangle[i][j] = newValue;
            }
        }
    }

    // Method to get the value at a specific position
    public int getValue(int row, int col) {
        return this.rectangle[row][col];
    }

}

3. Subrectangle Queries solution in Python Try on Compiler 
class SubrectangleQueries:
    
    # Constructor to initialize the rectangle
    def __init__(self, rectangle):
        self.rectangle = rectangle

    # Method to update a subrectangle with a new value
    def updateSubrectangle(self, row1, col1, row2, col2, newValue):

        # Iterate through the rows within the specified range
        for i in range(row1, row2 + 1):
            
            # Iterate through the columns within the specified range
            for j in range(col1, col2 + 1):
                
                # Update the cell value to the new value
                self.rectangle[i][j] = newValue

    # Method to get the value at a specific position
    def getValue(self, row, col):
        return self.rectangle[row][col]

4. Subrectangle Queries solution in JavaScript Try on Compiler 
// Import file system module for input reading
const fs = require("fs"); 

/**
 * @param {number[][]} rectangle
 */
var SubrectangleQueries = function(rectangle) {

    // Store the rectangle (matrix)
    this.rectangle = rectangle;
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2 
 * @param {number} newValue
 * @return {void}
 */
SubrectangleQueries.prototype.updateSubrectangle = function(row1, col1, row2, col2, newValue) {

    // Iterate over the given subrectangle and update all its elements
    for (let i = row1; i <= row2; i++) {
        for (let j = col1; j <= col2; j++) {
            this.rectangle[i][j] = newValue;
        }
    }
};

/** 
 * @param {number} row 
 * @param {number} col
 * @return {number}
 */
SubrectangleQueries.prototype.getValue = function(row, col) {

    // Return the value directly from the matrix
    return this.rectangle[row][col];
};

Complexity Analysis of the problem

Time Complexity: O(r x c)

  • The constructor initializes the object with the given rectangle by storing a reference to it, which takes O(1).
  • The updateSubrectangle(row1, col1, row2, col2, newValue) method:
    → Iterates from row1 to row2, contributing O(r).
    → Iterates from col1 to col2, contributing O(c).
    → Updates each element in the subrectangle, leading to O(1) work per update.
    → Overall, this results in O(r × c) complexity per update.
  • The getValue(row, col) method: Directly accesses the element in O(1) time.
  • If all 500 operations are updateSubrectangle, the worst complexity would be O(500 × r × c) = O(r x c).
  • Thus, the total time complexity becomes O(r x c)

Space Complexity: O(r x c)

Auxiliary Space Complexity refers to the extra space required by an algorithm beyond the input space. In this case, no additional data structures are used apart from the input rectangle. Only a few integer variables are required to track indices during updates, making the auxiliary space O(1).

Total Space Complexity: The total space complexity includes the space used by the input rectangle. Since we store the given rectangle as a r × c matrix, the overall space complexity remains O(r × c).

Overall Space Complexity: O(r × c).

Looking at the constraints where the number of operations is at most 500 and the grid size is 100 × 100, the brute force approach efficiently updates the subrectangle in O(r × c) time per operation. This ensures that each update modifies the required elements directly, making retrieval operations O(1).

While this approach works well within the given constraints, we can explore other techniques to optimize updates further, especially when the number of updates is large.

Optimal Approach

Intuition

We have a rectangle (matrix) where certain regions need to be updated, and values must be retrieved efficiently. When we get an update request for a subrectangle, modifying every affected cell directly is inefficient, especially if there are numerous updates. A naive approach would be to loop over all the affected cells and change them immediately, but what if we get thousands of updates? Each one would require modifying a large portion of the matrix, significantly increasing time complexity.

So, let’s think of this problem differently and find a smarter way to handle updates and retrievals.

Let's take a 3×3 matrix as an example:

Initial Matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Now, let’s perform some update operations on different subrectangles:

🔹Update [0,0] to [1,1] → New Value = 10

[[10, 10, 3], [10, 10, 6], [7, 8, 9]]

🔹Update [1,0] to [2,1] → New Value = 20

[[10, 10, 3]. [20, 20, 6], [20, 20, 9]]

🔹Update [2,2] to [2,2] → New Value = 30

[[10, 10, 3], [20, 20, 6], [20, 20, 30]]

🔹Update [1,1] to [2,2] → New Value = 40

[[10, 10, 3], [20, 40, 40], [20, 40, 40]]

Now, let’s retrieve some values and see how they were updated:

🔹 getValue(2,2) → 40
(Originally 9 → Updated to 30 → Updated again to 40)

🔹 getValue(1,1) → 40
(Originally 5 → Updated to 10 → Updated to 40)

🔹 getValue(1,0) → 20
(Originally 4 → Updated to 10 → Updated to 20)

🔹 getValue(0,2) → 3
(This cell was never updated, so we return the original value)

So, from the above observations, we can say that to retrieve a value efficiently, we only need to check the latest updates that might have affected that cell. If a cell was updated multiple times, the most recent update overrides all previous ones. If a cell was never updated, we simply return its original value from the matrix.

Storing and Retrieving Updates Efficiently

Instead of modifying the matrix directly, we can store the update operations in a list. When a getValue operation is called, we iterate through this list to check if any update affected the requested cell.

  • To easily get the latest update, we should store the updates at the front of the list. That way, we can start the iteration from the beginning and find the latest update quickly.
  • If we find an update operation that covers the cell, we return the newValue from that operation.
  • If we iterate through the entire list without finding a matching update, we return the original value from the matrix.

For this approach, a LinkedList is more suitable than an ArrayList. Before we delve into why a LinkedList is better than an ArrayList, let's recap what a LinkedList is.

What is a LinkedList?

A LinkedList is a data structure where elements (nodes) are stored sequentially, and each node contains:

  • Data (the actual value).
  • Pointer to the next node in the list.

Unlike arrays, a LinkedList allows efficient insertions and deletions at any position without shifting elements.

Example: LinkedList of Integers
9 → 5 → 1 → 8 → 10 → null 

Example: LinkedList of Arrays (Updates Stored as Arrays)
[1, 1, 2, 2, 40] → [2, 2, 2, 2, 30] → [1, 0, 2, 1, 20] → [0, 0, 1, 1, 10] → null

Why use a LinkedList instead of an ArrayList?

An ArrayList is backed by an array, meaning:

  • Insertions at the beginning (addFirst) require shifting all elements, making it O(n).
  • It has a fixed-size capacity, which may require resizing, leading to performance overhead.

Since we frequently insert updates at the beginning, a LinkedList is better because addFirst() takes O(1) time, avoiding expensive shifts.

By using a LinkedList to store updates, we efficiently keep track of changes without modifying the matrix directly. When retrieving a value, we simply check the most recent updates first, ensuring optimal performance while avoiding unnecessary computations.

Subrectangle Queries Algorithm

  1. We store the given matrix rectangle in an instance variable.
  2. We use a LinkedList to store update operations instead of modifying the matrix directly.
  3. We implement the updateSubrectangle method to store the update parameters {row1, row2, col1, col2, newValue} at the beginning of the list using addFirst().
  4. We implement the getValue method to retrieve the current value at (row, col).
    i. We first check the original rectangle[row][col].
    ii. We then iterate through the stored updates in the LinkedList (starting from the most recent) to check if (row, col) lies within an update range.
    iii. If found, we return the corresponding newValue.
  5. This avoids modifying the matrix multiple times, optimizing update operations.

Approach

Initialize Variables:

    • Store the given matrix rectangle in an instance variable.
    • Maintain a LinkedList<int[]> named list to store update operations.

Update Operation (updateSubrectangle):

    • Instead of modifying the matrix directly, store the update operation as an array {row1, row2, col1, col2, newValue} in list.
    • Use addFirst() to keep the most recent update at the front for quick access.

Retrieve Value (getValue):

    • Start with the original value from rectangle[row][col].
    • Iterate through the list from most recent to oldest updates.
    • If the given (row, col) falls within any stored update range {row1, row2, col1, col2}, return newValue.
    • If no update applies, return the original value from rectangle.

Return Final Value: The latest valid update for (row, col) is returned, ensuring efficient query resolution.

Dry-Run

General Setup:
Input: ["SubrectangleQueries", "getValue", "updateSubrectangle", "getValue", "getValue", "updateSubrectangle", "getValue"]
[[[[5, 6, 7], [8, 9, 10], [11, 12, 13]]], [1, 1], [0, 0, 2, 1, 50], [0, 1], [2, 1], [1, 0, 2, 2, 99], [2, 2]]
Output: [null, 9, null, 50, 50, null, 99]

Step-by-Step Execution:

Initialize SubrectangleQueries

  • Operation: SubrectangleQueries([[5, 6, 7], [8, 9, 10], [11, 12, 13]])
  • Action: Store the matrix but do not modify it during updates.
  • Updates List: [] (Empty)
  • Output: null

getValue(1,1)

  • Operation: getValue(1, 1)
  • Action: No updates exist yet.
  • Retrieve value from the original matrix: matrix[1][1] = 9
  • Output: 9
  • Updates List: []

updateSubrectangle(0,0,2,1,50)

  • Operation: updateSubrectangle(0, 0, 2, 1, 50)
  • Action: Store the update at the front of the list.
  • Updates List: [[0, 0, 2, 1, 50]]
  • Matrix is NOT modified directly.
  • Output: null

getValue(0,1)

  • Operation: getValue(0,1)
  • Action:
    → Check the updates list from the latest to the oldest.
    → Update [0,0,2,1,50] covers (0,1), so return 50 instead of matrix[0][1] = 6.
  • Output: 50
  • Updates List: [[0, 0, 2, 1, 50]]

getValue(2,1)

  • Operation: getValue(2,1)
  • Action:
    → Check the updates list from the latest to the oldest.
    → Update [0,0,2,1,50] covers (2,1), so return 50 instead of matrix[2][1] = 12.
  • Output: 50
  • Updates List: [[0, 0, 2, 1, 50]]

updateSubrectangle(1,0,2,2,99)

  • Operation: updateSubrectangle(1, 0, 2, 2, 99)
  • Action: Store the update at the front of the list.
  • Updates List (most recent first): [[1, 0, 2, 2, 99], [0, 0, 2, 1, 50]]
  • Matrix is NOT modified directly.
  • Output: null

getValue(2,2)

  • Operation: getValue(2,2)
  • Action:
    → Check updates list from latest to oldest.
    → Update [1,0,2,2,99] covers (2,2), so return 99 instead of matrix[2][2] = 13.
  • Output: 99
  • Updates List: [[1, 0, 2, 2, 99], [0, 0, 2, 1, 50]]

Final Output:

[null, 9, null, 50, 50, null, 99]

Conclusion:

By using a LinkedList, we store updates efficiently instead of modifying the matrix directly. When retrieving values, we scan the updates list from most recent to oldest and return the latest valid update for the queried position. This optimizes the updateSubrectangle operation while ensuring quick getValue lookups.

Subrectangle Queries solution

Let now discover the codes for Subrectangle Queries problem in C++, Java, Python, and JavaScript

Optimal Code in all Languages
1. Subrectangle Queries solution in C++ Try on Compiler 
class SubrectangleQueries {
    
    // Store the original matrix
    vector<vector<int>> matrix;

    // List to store updates (each update contains {row1, col1, row2, col2, newValue})
    deque<array<int, 5>> updates;

public:
    
    // Constructor to initialize the matrix
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        matrix = rectangle;
    }

    
    // Function to store the update operation instead of modifying the matrix directly
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        
        // Add the update at the front of the list to maintain the latest updates first
        updates.push_front({row1, col1, row2, col2, newValue});
    }

    
    // Function to retrieve value at (row, col)
    int getValue(int row, int col) {
        
        // Iterate over the updates from most recent to oldest
        for (auto &update : updates) {
            
            // If the (row, col) lies within an updated subrectangle, return its value
            if (update[0] <= row && row <= update[2] && update[1] <= col && col <= update[3]) {
                return update[4];
            }
        }

        // If no updates apply, return the original matrix value
        return matrix[row][col];
    }
};

2. Subrectangle Queries solution in Java Try on Compiler 
class SubrectangleQueries {
    
    // Store the original matrix
    private int[][] matrix;

    // List to store updates (each update contains {row1, col1, row2, col2, newValue})
    private LinkedList<int[]> updates = new LinkedList<>();

    
    // Constructor to initialize the matrix
    public SubrectangleQueries(int[][] rectangle) {
        matrix = rectangle;
    }

    
    // Function to store the update operation instead of modifying the matrix directly
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        
        // Add the update at the front of the list to maintain the latest updates first
        updates.addFirst(new int[]{row1, col1, row2, col2, newValue});
    }

    
    // Function to retrieve value at (row, col)
    public int getValue(int row, int col) {
        
        // Iterate over the updates from most recent to oldest
        for (int[] update : updates) {
            
            // If the (row, col) lies within an updated subrectangle, return its value
            if (update[0] <= row && row <= update[2] && update[1] <= col && col <= update[3]) {
                return update[4];
            }
        }

        // If no updates apply, return the original matrix value
        return matrix[row][col];
    }
    
}

3. Subrectangle Queries solution in Python Try on Compiler 
class SubrectangleQueries:
    
    # Constructor to initialize the matrix and an update list
    def __init__(self, rectangle: List[List[int]]):
        
        # Store the original matrix
        self.matrix = rectangle

        # List to store updates (each update contains [row1, col1, row2, col2, newValue])
        self.updates = []

    
    # Function to store the update operation instead of modifying the matrix directly
    def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
        
        # Add the update at the front of the list to maintain the latest updates first
        self.updates.insert(0, [row1, col1, row2, col2, newValue])

    
    # Function to retrieve value at (row, col)
    def getValue(self, row: int, col: int) -> int:
        
        # Iterate over the updates from most recent to oldest
        for r1, c1, r2, c2, val in self.updates:
            
            # If the (row, col) lies within an updated subrectangle, return its value
            if r1 <= row <= r2 and c1 <= col <= c2:
                return val

        # If no updates apply, return the original matrix value
        return self.matrix[row][col]

4. Subrectangle Queries solution in JavaScript Try on Compiler 
const fs = require("fs");

/**
 * @param {number[][]} rectangle
 */

 
// Constructor function to initialize the matrix and an array to store updates
var SubrectangleQueries = function(rectangle) {
    
    // Store the initial rectangle matrix
    this.matrix = rectangle;

    // List to store updates (each update is an array of [row1, col1, row2, col2, newValue])
    this.updates = [];
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2 
 * @param {number} newValue
 * @return {void}
 */

 
// Function to store the update operation instead of modifying the matrix directly
SubrectangleQueries.prototype.updateSubrectangle = function(row1, col1, row2, col2, newValue) {
    
    // Add the update details at the beginning of the updates list (to keep latest updates at the front)
    this.updates.unshift([row1, col1, row2, col2, newValue]);
};

/** 
 * @param {number} row 
 * @param {number} col
 * @return {number}
 */

 
// Function to get the value at (row, col) by checking the updates list first
SubrectangleQueries.prototype.getValue = function(row, col) {
    
    // Iterate over updates list from the most recent to the oldest
    for (const [r1, c1, r2, c2, val] of this.updates) {
        
        // If the (row, col) falls within the range of an update, return the updated value
        if (row >= r1 && row <= r2 && col >= c1 && col <= c2) {
            return val;
        }
    }

    // If no updates apply, return the original matrix value
    return this.matrix[row][col];
};

Time Complexity: O(u)

  • The constructor initializes the object with the given rectangle by storing a reference to it, which takes O(1).
  • The updateSubrectangle(row1, col1, row2, col2, newValue) method:
    → Adding an update operation to the LinkedList takes O(1) (inserting at the front).
  • The getValue(row, col) method:
    → In the worst case, it checks O(u) updates before returning a value.
    → Thus, the worst-case complexity is O(u), where 'u' is the number of stored updates.
  • Final Time Complexity:
    → constructor: O(1)
    → updateSubrectangle: O(1)
    → getValue: O(u) in the worst case
  • Overall Time Complexity: O(u)

Space Complexity: O(r x c + u)

Auxiliary Space Complexity refers to the extra space required by an algorithm beyond the input space. In this case, we maintain a LinkedList<int[]> to store update operations. Each update operation stores a fixed-size array of 5 integers, leading to O(u) auxiliary space, where u is the number of update operations.

Total Space Complexity: The total space complexity includes both the input grid and any additional data structures. The input grid takes O(r × c) space, and the update list takes O(u) space.

Thus, the overall space complexity is O(r × c + u). Overall Space Complexity: O(r × c + u).

Similar Problems

Now, since we have figured out the Find the Minimum Area to Cover All Ones I solution, let's try out similar problems of "Find the Minimum Area to Cover All Ones I".

Smallest Rectangle Enclosing Black Pixels

Find the minimum area to cover all ones ii

You are given a 2D binary array grid. You need to find 3 non-overlapping rectangles having non-zero areas with horizontal and vertical sides such that all the 1's in grid lie inside these rectangles.

Return the minimum possible sum of the area of these rectangles.

Note that the rectangles are allowed to touch.