Skip to main content

Matrix

Find the Minimum Area to Cover All Ones I Solution In C++/Python/java/JS

Find the Minimum Area to Cover All Ones I Problem

You are given a 2D binary array grid. Find a rectangle with horizontal and vertical sides with the smallest area, such that all the 1's in grid lie inside this rectangle.

Return the minimum possible area of the rectangle.

Explanation

We are given a matrix (a table of numbers) where each cell contains either 0 or 1. Our goal is to find the smallest rectangle that covers all the 1's in the matrix and return the area of that rectangle.

What is a 2D Binary Array?

A 2D binary array is simply a 2D array (matrix) in which each element can only be 0 or 1. It follows the same row-column structure as a regular 2D array but is restricted to binary values of 0 and 1.

2D binary array example:
grid = [
[1, 0, 0, 1],
[0, 1, 1, 0],
[0, 0, 1, 0]
]

This is NOT a 2D binary array:
grid = [
[2, 0, 3, 1],
[5, 1, 1, 4],
[0, 7, 1, 8]
]
This matrix contains numbers like 2, 3, 5, 7, and 8, which are not allowed in a binary array.

Example

Input: grid = [[0,1,0],[1,0,1]]
Output: 6
Explanation:
The smallest rectangle has a height of 2 and a width of 3, so it has an area of 2 * 3 = 6.

Input: grid = [[1,0],[0,0]]
Output: 1
Explanation:
The smallest rectangle has both height and width 1, so its area is 1 * 1 = 1.

Constraints

  • 1 <= grid.length, grid[i].length <= 1000
  • grid[i][j] is either 0 or 1.
  • The input is generated such that there is at least one 1 in grid.
💡
Try Solving "Find the Minimum Area to Cover All Ones I" Yourself First!
"Find the Minimum Area to Cover All Ones I" Problem can be solved using different approaches, such as Brute Force and Optimized 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 check all possible rectangles in the grid and see which one contains all the 1's. We can then calculate the area of each valid rectangle and find the smallest one.

How to Generate All Possible Rectangles in a Matrix?

To generate all possible rectangles in a grid, we will use four nested loops:

  1. The first loop will iterate over each row to set the top boundary of the rectangle.
  2. The second loop will iterate over each column to set the left boundary of the rectangle.
  3. The third loop will iterate from the top boundary to the last row to set the bottom boundary of the rectangle.
  4. The fourth loop will iterate from the left boundary to the last column to set the right boundary of the rectangle.

For each combination of top, left, bottom, and right boundaries, we form a rectangle.

Example: Let's consider the grid = [ [0 1 0], [1 0 1]]

We will generate all possible rectangles:

Top boundary at row 0:

  1. Left boundary at column 0:
    → Bottom boundary at row 0, right boundary at column 0: Rectangle (0,0) to (0,0)
    → Bottom boundary at row 0, right boundary at column 1: Rectangle (0,0) to (0,1)
    → Bottom boundary at row 0, right boundary at column 2: Rectangle (0,0) to (0,2)
    → Bottom boundary at row 1, right boundary at column 0: Rectangle (0,0) to (1,0)
    → Bottom boundary at row 1, right boundary at column 1: Rectangle (0,0) to (1,1)
    → Bottom boundary at row 1, right boundary at column 2: Rectangle (0,0) to (1,2)
  2. Left boundary at column 1:
    → Bottom boundary at row 0, right boundary at column 1: Rectangle (0,1) to (0,1)
    → Bottom boundary at row 0, right boundary at column 2: Rectangle (0,1) to (0,2)
    → Bottom boundary at row 1, right boundary at column 1: Rectangle (0,1) to (1,1)
    → Bottom boundary at row 1, right boundary at column 2: Rectangle (0,1) to (1,2)
  3. Left boundary at column 2:
    → Bottom boundary at row 0, right boundary at column 2: Rectangle (0,2) to (0,2)
    → Bottom boundary at row 1, right boundary at column 2: Rectangle (0,2) to (1,2)

Top boundary at row 1:

  1. Left boundary at column 0:
    → Bottom boundary at row 1, right boundary at column 0: Rectangle (1,0) to (1,0)
    → Bottom boundary at row 1, right boundary at column 1: Rectangle (1,0) to (1,1)
    → Bottom boundary at row 1, right boundary at column 2: Rectangle (1,0) to (1,2)
  2. Left boundary at column 1:
    → Bottom boundary at row 1, right boundary at column 1: Rectangle (1,1) to (1,1)
    → Bottom boundary at row 1, right boundary at column 2: Rectangle (1,1) to (1,2)
  3. Left boundary at column 2:
    → Bottom boundary at row 1, right boundary at column 2: Rectangle (1,2) to (1,2)

By iterating through all these combinations, we can generate all possible rectangles in the grid. This way, we ensure that we check every possible rectangle to find the one with the smallest area that contains all the 1s.

Now that we have generated all possible rectangles, we need to check whether each rectangle contains all the 1's or not and then we compute and store the minimum area found.

How to Check if a Rectangle Contains All 1's?

To check if a rectangle contains all the 1's in the grid, we need to:

  1. Iterate over each cell in the grid.
  2. For each cell that contains a 1, verify if it lies within the boundaries of the rectangle (top, left, bottom, right).

Steps:

  1. Iterate over each cell in the grid:
    1. Use two nested loops to go through each row and column.
  2. Check if the cell contains a 1:
    1. If the cell contains a 1, check if its row and column indices are within the rectangle's boundaries.
  3. Verify boundaries:
    1. If any 1 is found outside the rectangle, the rectangle does not contain all the 1s.

Example: Let's consider the grid = [[0, 1, 0], [1, 0, 1]]

And a rectangle with boundaries (top=0, left=0, bottom=1, right=2).

  • Iterate over each cell:
    1. Cell (0,1) is 1 and within the rectangle.
    2. Cell (1,0) is 1 and within the rectangle.
    3. Cell (1,2) is 1 and within the rectangle.

Since all 1s are within the rectangle, it contains all the 1s.

Find the Minimum Area to Cover All Ones I Algorithm

  1. We iterate over all possible rectangles by selecting top-left and bottom-right corners.
  2. For each rectangle, we check if it encloses all '1's.
  3. We calculate the area of valid rectangles and track the minimum.
  4. To verify containment, we scan the entire grid for any '1' outside the selected rectangle.
  5. Finally, we return the smallest valid area or 0 if no '1' exists.

Approach

Initialize Variables:

  • When we start, we need to initialize a few variables:
  • minArea to keep track of the smallest area found.
  • rows and cols to store the number of rows and columns in the grid.

Check all possible rectangles:

  • We will use four nested loops to iterate over all possible rectangles:
  • The first loop will set the top boundary of the rectangle.
  • The second loop will set the left boundary of the rectangle.
  • The third loop will set the bottom boundary of the rectangle.
  • The fourth loop will set the right boundary of the rectangle.

Verify each rectangle

  • For each rectangle defined by the top, left, bottom, and right boundaries, we will check if it contains all the 1s in the grid.

Calculate the area:

  • If a rectangle contains all the 1s, we will calculate its area using the formula:
  • Area = (bottom−top+1) × (right−left+1)
  • We will update minArea if the current rectangle's area is smaller.

Return Result:

  • If a valid minimum area rectangle that contains all the 1s was found, return its area. If no valid rectangle was found, return 0.

Dry-Run

General Setup:
Input Grid: grid = [[0, 1, 0], [1, 0, 1]]
Output Area = 6

Objective: Find the smallest rectangle that contains all 1s in the grid.

Step-by-Step Dry Run

Step 1: Iterate Over All Possible Rectangles
We try all possible (top, left, bottom, right) coordinates to define rectangles.

Dry Run for (top = 0, left = 0)

We check all possible bottom-right coordinates expanding from (0,0).

  1. Rectangle (0,0) to (0,0): [0]
    Does it contain all 1s? No.
  2. Rectangle (0,0) to (0,1): [0, 1]
    Does it contain all 1s? No.
  3. Rectangle (0,0) to (0,2): [0, 1, 0]
    Does it contain all 1s? No.
  4. Rectangle (0,0) to (1,2): [[0,1,0],[1,0,1]]
    Does it contain all 1s? Yes.
    Update minArea: Current area = (1-0+1) * (2-0+1) = 2 * 3 = 6.

Dry Run for (top = 0, left = 1)

We start at index (0,1) and expand.

  1. Rectangle (0,1) to (0,1): [1]
    Does it contain all 1s? No.
  2. Rectangle (0,1) to (1,1): [1, 0]
    Does it contain all 1s? No.
  3. Rectangle (0,1) to (1,2): [[1, 0],[0, 1]]
    Does it contain all 1s? No.

Dry Run for (top = 1, left = 0)

We start at index (1,0).

  1. Rectangle (1,0) to (1,0):[1]
    Does it contain all 1s? No.
  2. Rectangle (1,0) to (1,2):[1,0,1]
    Does it contain all 1s? No.

Final Result

The smallest rectangle found was from (0,0) to (1,2) with an area of 6.

Summary

  • For (0,0) to (1,2), we found the first valid rectangle (area = 6).
  • We continue checking smaller ones but don’t find a smaller valid rectangle.
  • The final answer remains 6.

🔹 Final Output: 6

Find the Minimum Area to Cover All Ones I solution

Let now discover the codes for Find the Minimum Area to Cover All Ones I problem in C++, Java, Python, and JavaScript

Brute Force Code in all Languages.
1. Find the Minimum Area to Cover All Ones I solution in C++ Try on Compiler 
class Solution {
public:
    // Function to find the minimum area of a rectangle containing all '1's
    int minimumArea(vector<vector<int>>& grid) {
        // Get the number of rows in the grid
        int rows = grid.size();

        // Get the number of columns in the grid
        int cols = grid[0].size();

        // Initialize the minimum area with a large value
        int minArea = INT_MAX;

        // Loop to select the top boundary of the rectangle
        for (int top = 0; top < rows; top++) {
            
            // Loop to select the left boundary of the rectangle
            for (int left = 0; left < cols; left++) {
                
                // Loop to select the bottom boundary of the rectangle
                for (int bottom = top; bottom < rows; bottom++) {
                    
                    // Loop to select the right boundary of the rectangle
                    for (int right = left; right < cols; right++) {
                        
                        // Check if this rectangle contains all '1's from the grid
                        if (allOnesInside(grid, top, left, bottom, right)) {
                            
                            // Calculate the area of the rectangle
                            int area = (bottom - top + 1) * (right - left + 1);
                            
                            // Update the minimum area if the new area is smaller
                            minArea = min(minArea, area);
                        }
                    }
                }
            }
        }

        // Return the minimum area found, or 0 if no '1' was found
        return minArea == INT_MAX ? 0 : minArea;
    }

private:
    // Helper function to check if all '1's in the grid are inside the given rectangle
    bool allOnesInside(vector<vector<int>>& grid, int top, int left, int bottom, int right) {
        
        // Flag to check if there is at least one '1' in the grid
        bool hasOne = false;

        // Loop through each row in the grid
        for (int r = 0; r < grid.size(); r++) {
            
            // Loop through each column in the grid
            for (int c = 0; c < grid[0].size(); c++) {
                
                // If the current cell contains a '1'
                if (grid[r][c] == 1) {
                    
                    // Mark that at least one '1' exists
                    hasOne = true;
                    
                    // Check if this '1' is outside the given rectangle
                    if (r < top || r > bottom || c < left || c > right) {
                        
                        // If any '1' is outside, return false
                        return false;
                    }
                }
            }
        }

        // If no '1' was found in the entire grid, return false
        return hasOne;
    }
};

2. Find the Minimum Area to Cover All Ones I solution in Java Try on Compiler 
// Solution class to find the minimum area of a rectangle containing all '1's
class Solution {
    
    // Function to find the minimum area of a rectangle that contains all '1's
    public int minimumArea(int[][] grid) {
        
        // Get the number of rows in the grid
        int rows = grid.length;

        // Get the number of columns in the grid
        int cols = grid[0].length;

        // Initialize the minimum area with a large value
        int minArea = Integer.MAX_VALUE;

        // Loop to select the top boundary of the rectangle
        for (int top = 0; top < rows; top++) {
            
            // Loop to select the left boundary of the rectangle
            for (int left = 0; left < cols; left++) {
                
                // Loop to select the bottom boundary of the rectangle
                for (int bottom = top; bottom < rows; bottom++) {
                    
                    // Loop to select the right boundary of the rectangle
                    for (int right = left; right < cols; right++) {
                        
                        // Check if this rectangle contains all '1's from the grid
                        if (allOnesInside(grid, top, left, bottom, right)) {
                            
                            // Calculate the area of the rectangle
                            int area = (bottom - top + 1) * (right - left + 1);
                            
                            // Update the minimum area if the new area is smaller
                            minArea = Math.min(minArea, area);
                        }
                    }
                }
            }
        }

        // Return the minimum area found
        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }

    // Helper function to check if all '1's in the grid are inside the given rectangle
    private boolean allOnesInside(int[][] grid, int top, int left, int bottom, int right) {
        
        // Flag to check if there is at least one '1' in the grid
        boolean hasOne = false;

        // Loop through each row in the grid
        for (int r = 0; r < grid.length; r++) {
            
            // Loop through each column in the grid
            for (int c = 0; c < grid[0].length; c++) {
                
                // If the current cell contains a '1'
                if (grid[r][c] == 1) {
                    
                    // Mark that at least one '1' exists
                    hasOne = true;
                    
                    // Check if this '1' is outside the given rectangle
                    if (r < top || r > bottom || c < left || c > right) {
                        
                        // If any '1' is outside, return false
                        return false;
                    }
                }
            }
        }

        // If no '1' was found in the entire grid, return false
        return hasOne;
    }
}

3. Find the Minimum Area to Cover All Ones I solution in Python Try on Compiler 
class Solution:
    
    # Function to find the minimum area of a rectangle that contains all '1's
    def minimumArea(self, grid: List[List[int]]) -> int:
        
        # Get the number of rows in the grid
        rows = len(grid)
        
        # Get the number of columns in the grid
        cols = len(grid[0])
        
        # Initialize the minimum area with a large value
        min_area = sys.maxsize
        
        # Loop to select the top boundary of the rectangle
        for top in range(rows):
            
            # Loop to select the left boundary of the rectangle
            for left in range(cols):
                
                # Loop to select the bottom boundary of the rectangle
                for bottom in range(top, rows):
                    
                    # Loop to select the right boundary of the rectangle
                    for right in range(left, cols):
                        
                        # Check if this rectangle contains all '1's from the grid
                        if self.all_ones_inside(grid, top, left, bottom, right):
                            
                            # Calculate the area of the rectangle
                            area = (bottom - top + 1) * (right - left + 1)
                            
                            # Update the minimum area if the new area is smaller
                            min_area = min(min_area, area)
        
        # Return the minimum area found, or 0 if no '1' was found
        return 0 if min_area == sys.maxsize else min_area
    
    # Helper function to check if all '1's in the grid are inside the given rectangle
    def all_ones_inside(self, grid: List[List[int]], top: int, left: int, bottom: int, right: int) -> bool:
        
        # Flag to check if there is at least one '1' in the grid
        has_one = False
        
        # Loop through each row in the grid
        for r in range(len(grid)):
            
            # Loop through each column in the grid
            for c in range(len(grid[0])):
                
                # If the current cell contains a '1'
                if grid[r][c] == 1:
                    
                    # Mark that at least one '1' exists
                    has_one = True
                    
                    # Check if this '1' is outside the given rectangle
                    if r < top or r > bottom or c < left or c > right:
                        
                        # If any '1' is outside, return False
                        return False
        
        # If no '1' was found in the entire grid, return False
        return has_one

4. Find the Minimum Area to Cover All Ones I solution in JavaScript Try on Compiler 
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var minimumArea = function(matrix) {
    
    // Get the number of rows in the grid
    const rows = matrix.length;
    
    // Get the number of columns in the grid
    const cols = matrix[0].length;
    
    // Initialize the minimum area with a large value
    let minArea = Infinity;
    
    // Loop to select the top boundary of the rectangle
    for (let top = 0; top < rows; top++) {
        
        // Loop to select the left boundary of the rectangle
        for (let left = 0; left < cols; left++) {
            
            // Loop to select the bottom boundary of the rectangle
            for (let bottom = top; bottom < rows; bottom++) {
                
                // Loop to select the right boundary of the rectangle
                for (let right = left; right < cols; right++) {
                    
                    // Check if this rectangle contains all '1's from the grid
                    if (allOnesInside(matrix, top, left, bottom, right)) {
                        
                        // Calculate the area of the rectangle
                        let area = (bottom - top + 1) * (right - left + 1);
                        
                        // Update the minimum area if the new area is smaller
                        minArea = Math.min(minArea, area);
                    }
                }
            }
        }
    }
    
    // Return the minimum area found, or 0 if no rectangle is found
    return minArea === Infinity ? 0 : minArea;
};

/**
 * Helper function to check if all '1's in the grid are inside the given rectangle
 * @param {number[][]} matrix
 * @param {number} top
 * @param {number} left
 * @param {number} bottom
 * @param {number} right
 * @return {boolean}
 */
function allOnesInside(matrix, top, left, bottom, right) {
    
    // Flag to check if there is at least one '1' in the grid
    let hasOne = false;
    
    // Loop through each row in the grid
    for (let r = 0; r < matrix.length; r++) {
        
        // Loop through each column in the grid
        for (let c = 0; c < matrix[0].length; c++) {
            
            // If the current cell contains a '1'
            if (matrix[r][c] === 1) {
                
                // Mark that at least one '1' exists
                hasOne = true;
                
                // Check if this '1' is outside the given rectangle
                if (r < top || r > bottom || c < left || c > right) {
                    
                    // If any '1' is outside, return false
                    return false;
                }
            }
        }
    }
    
    // If no '1' was found in the entire grid, return false
    return hasOne;
}

Complexity Analysis of the problem

Time Complexity: O(n³ * m³)

The approach utilizes four nested loops, leading to a time complexity of O(n × m × n × m), where n is the number of rows and m is the number of columns in the grid. Here’s a detailed breakdown:

  • The outermost loop iterates over each row to set the top boundary, contributing O(n).
  • The second loop iterates over each column to set the left boundary, contributing O(m).
  • The third loop iterates from the top boundary to the bottom, contributing O(n).
  • The fourth loop iterates from the left boundary to the right, contributing O(m).
  • Inside the loops, we check whether all 1s are inside the current rectangle using another O(n × m) operation in the worst case.

Thus, the total time complexity becomes O(n² × m² × n × m) = O(n³ × m³). This is highly inefficient for large grids, as the execution time increases rapidly with input size

Space Complexity: O(n*m)

  • Auxiliary space Complexity refers to the extra space required by an algorithm other than the input space. In this case, it is constant, O(1), because we only use a few integer variables to track indices and the minimum area. No additional data structures are used.
  • Total space Complexity:
    The total space complexity considers the space used by the input grid. Since we do not create additional data structures beyond the input, the overall space complexity remains O(n*m), where n is the number of rows and m is the number of columns.
    Overall space complexity: O(n*m).

Overall space complexity: O(n*m).

Looking at the constraints where the size of the grid is 1000 × 1000, the brute force approach results in Time Limit Exceeded since checking all possible rectangles takes O(n³ * m³) time in the worst case, which is highly inefficient. The interviewer will be unhappy with this solution. Let's figure out a optimal approach.

Optimal Approach

Intuition

For our problem, we need to find the area of a single rectangle that encloses all the 1s in the grid. But instead of checking every possible rectangle like we did in the brute force approach, we can be much smarter.

Think of it this way: Which rectangle should we consider?

Look at these different grids below

grid = [[0, 1], [0, 0]]
grid = [[0, 0], [1, 1]]
grid = [[]]
Our goal is always to find the smallest rectangle that covers all the 1s. That’s the only rectangle that matters!

How Do We Find This Rectangle?
To define a rectangle, we need to know its boundaries. In simpler terms, we need to find:
1. The topmost row that contains a 1.

2. The bottommost row that contains a 1.

3. The leftmost column that contains a 1.

  1. The rightmost column that contains a 1.

Now that we have these four boundaries, the rectangle enclosing all the 1s is clearly defined. And since we already know that the area of a rectangle is calculated using:

Area = (bottom - top + 1) × (right - left + 1)

Why Do We Only Need These Four Boundaries?

To enclose all the 1s in a rectangle, we only care about the extreme positions where a '1' appears. Why?

  • The topmost row containing a '1' ensures there are no 1s above it, so we don't need to extend the rectangle further up.
  • The bottommost row containing a '1' ensures there are no 1s below it, so we don’t need to extend further down.
  • The leftmost column containing a '1' ensures there are no 1s to the left, so we don’t need to expand the rectangle to the left.
  • The rightmost column containing a '1' ensures there are no 1s to the right, so we don’t need to expand further to the right.

By capturing just these four values, we guarantee that every single '1' is enclosed, and the rectangle is as small as possible.

Why Not Consider Other Rows or Columns?

If we look at any row above the top boundary or any column left of the left boundary, they will only contain '0's. Including them in our rectangle would unnecessarily increase its area. Similarly, going beyond the bottom or right boundary would also add only '0's.

Thus, instead of scanning every possible rectangle, we can directly compute the minimum enclosing area with these four boundaries.

Example Walkthrough:

Input grid: [[0, 1, 0], [1, 0, 1]]

Finding the Boundaries:

  • Topmost '1' appears at row 0 → top = 0
  • Bottommost '1' appears at row 1 → bottom = 1
  • Leftmost '1' appears at column 0 → left = 0
  • Rightmost '1' appears at column 2 → right = 2

Final Computation:

  • Height = (1−0+1) =2
  • Width = (2−0+1) = 3
  • Area = 2×3 = 6

Thus, the minimum enclosing rectangle has an area of 6.

Find the Minimum Area to Cover All Ones I Algorithm

  1. We iterate through the grid to find all '1's.
  2. We track the topmost, bottommost, leftmost, and rightmost positions of '1's.
  3. If no '1' is found, we return 0.
  4. Otherwise, we compute the height and width using the recorded boundaries.
  5. We return the area of the enclosing rectangle.

Approach

Initialize Variables

  • topmost = Integer.MAX_VALUE → Tracks the smallest row index containing a 1 (top boundary).
  • bottommost = Integer.MIN_VALUE → Tracks the largest row index containing a 1 (bottom boundary).
  • leftmost = Integer.MAX_VALUE → Tracks the smallest column index containing a 1 (left boundary).
  • rightmost = Integer.MIN_VALUE → Tracks the largest column index containing a 1 (right boundary).

Why These Initial Values?

topmost and leftmost start at the maximum possible values to ensure they are updated to the smallest encountered indices.

bottommost and rightmost start at the minimum possible values to ensure they are updated to the largest encountered indices.

Single Pass to Determine Boundaries:

Iterate through the grid:
If grid[i][j] == 1:

  • Update topmost → min(topmost, i) (smallest row index).
  • Update bottommost → max(bottommost, i) (largest row index).
  • Update leftmost → min(leftmost, j) (smallest column index).
  • Update rightmost → max(rightmost, j) (largest column index).

Compute Area:

  • Formula: Area=(bottommost−topmost+1)×(rightmost−leftmost+1)

Return the Result:

  • If no 1 is found in the grid, return 0.
  • Otherwise, return the computed area.

Dry-Run

Example
Input:
grid = [[0, 0, 1, 0],
[0, 1, 1, 0],
[0, 1, 0, 0]]

Step-by-Step Execution:

  1. Start scanning the grid from (0,0).
    i. (0,0) is 0, so move ahead.
    ii. (0,1) is 0, so move ahead.
    iii. (0,2) is 1. Since this is the first 1 found, we initialize our boundaries:
    → topmost = 0
    → bottommost = 0
    → leftmost = 2
    → rightmost = 2
  2. Continue scanning row 0:
    i. (0,3) is 0, so no changes.
  3. Move to row 1:
    i. (1,0) is 0, so move ahead.
    ii. (1,1) is 1:
    → topmost remains 0 (already found earlier).
    → bottommost is updated to 1.
    → leftmost is updated to 1 (since 1 < 2).
    → rightmost remains 2.
    iii. (1,2) is 1:
    → No changes to topmost and leftmost.
    → bottommost is updated to 1.
    → rightmost remains 2.
    iv. (1,3) is 0, so no changes.
  4. Move to row 2:
    i. (2,0) is 0, so move ahead.
    ii. (2,1) is 1:
    → topmost remains 0.
    → bottommost is updated to 2.
    → leftmost remains 1.
    → rightmost remains 2.
    iii. (2,2) is 0, so no changes.
    iv. (2,3) is 0, so no changes.

Final Boundaries:

  • topmost = 0
  • bottommost = 2
  • leftmost = 1
  • rightmost = 2

Compute the Area:

Height = (bottommost - topmost + 1) = (2 - 0 + 1) = 3 

Width = (rightmost - leftmost + 1) = (2 - 1 + 1) = 2 

Area = Height × Width = 3 × 2 = 6

Output: 6

Find the Minimum Area to Cover All Ones I solution

Let now discover the codes for Find the Minimum Area to Cover All Ones I problem in C++, Java, Python, and JavaScript

Optimal Code in all Languages
1. Find the Minimum Area to Cover All Ones I solution in C++ Try on Compiler 
class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        
        // Number of rows
        int n = grid.size();    
        
         // Number of columns
        int m = grid[0].size();     

        // Variables to store the boundaries of the smallest enclosing rectangle
        int topmost = n, bottommost = -1, leftmost = m, rightmost = -1;

        // Brute Force: Checking every cell in the grid
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                
                // If we find a '1', update the boundaries
                if (grid[i][j] == 1) {
                    
                    // Update the topmost row containing '1'
                    if (i < topmost) topmost = i;
                    
                    // Update the bottommost row containing '1'
                    if (i > bottommost) bottommost = i;
                    
                    // Update the leftmost column containing '1'
                    if (j < leftmost) leftmost = j;
                    
                    // Update the rightmost column containing '1'
                    if (j > rightmost) rightmost = j;
                }
            }
        }

        // If no '1' was found, return area as 0
        if (bottommost == -1) return 0;
        
        // Compute the area of the enclosing rectangle
        int height = (bottommost - topmost + 1);
        int width = (rightmost - leftmost + 1);
        return height * width;
    }
};

2. Find the Minimum Area to Cover All Ones I solution in Java Try on Compiler 
class Solution {
    public int minimumArea(int[][] grid) {
        
         // Number of rows
        int n = grid.length;      
        
        // Number of columns
        int m = grid[0].length;    

        // Variables to store the boundaries of the smallest enclosing rectangle
        int topmost = n, bottommost = -1, leftmost = m, rightmost = -1;

        // Brute Force: Checking every cell in the grid
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                // If we find a '1', update the boundaries
                if (grid[i][j] == 1) {

                    // Update the topmost row containing '1'
                    if (i < topmost) topmost = i;

                    // Update the bottommost row containing '1'
                    if (i > bottommost) bottommost = i;

                    // Update the leftmost column containing '1'
                    if (j < leftmost) leftmost = j;

                    // Update the rightmost column containing '1'
                    if (j > rightmost) rightmost = j;
                }
            }
        }

        // If no '1' was found, return area as 0
        if (bottommost == -1) return 0;

        // Compute the area of the enclosing rectangle
        int height = (bottommost - topmost + 1);
        int width = (rightmost - leftmost + 1);
        return height * width;
    }
}

3. Find the Minimum Area to Cover All Ones I solution in Python Try on Compiler 
class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        
        # Number of rows in the grid
        n = len(grid)
        
        # Number of columns in the grid
        m = len(grid[0])
        
        # Variables to store the boundaries of the smallest enclosing rectangle

         # Topmost row containing '1'
        topmost = n     

        # Bottommost row containing '1'
        bottommost = -1    

        # Leftmost column containing '1'
        leftmost = m  

        # Rightmost column containing '1'
        rightmost = -1     

        # Iterate through the entire grid to find the boundaries
        for i in range(n):
            for j in range(m):
                
                # If we find a '1', update the boundaries
                if grid[i][j] == 1:
                    
                    # Update the topmost row containing '1'
                    topmost = min(topmost, i)

                    # Update the bottommost row containing '1'
                    bottommost = max(bottommost, i)

                    # Update the leftmost column containing '1'
                    leftmost = min(leftmost, j)

                    # Update the rightmost column containing '1'
                    rightmost = max(rightmost, j)

        # If no '1' was found in the grid, return area as 0
        if bottommost == -1:
            return 0

        # Compute the height of the enclosing rectangle
        height = (bottommost - topmost + 1)

        # Compute the width of the enclosing rectangle
        width = (rightmost - leftmost + 1)

        # Return the computed area
        return height * width

4. Find the Minimum Area to Cover All Ones I solution in JavaScript Try on Compiler 
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var minimumArea = function(matrix) {
    
    // Get the number of rows in the grid
    const rows = matrix.length;
    
    // Get the number of columns in the grid
    const cols = matrix[0].length;
    
    // Variables to store the boundaries of the smallest enclosing rectangle
    let topmost = rows, bottommost = -1, leftmost = cols, rightmost = -1;
    
    // Loop through each cell in the grid
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            
            // If we find a '1', update the boundaries
            if (matrix[i][j] === 1) {
                
                // Update the topmost row containing '1'
                if (i < topmost) topmost = i;
                
                // Update the bottommost row containing '1'
                if (i > bottommost) bottommost = i;
                
                // Update the leftmost column containing '1'
                if (j < leftmost) leftmost = j;
                
                // Update the rightmost column containing '1'
                if (j > rightmost) rightmost = j;
            }
        }
    }
    
    // If no '1' was found, return area as 0
    if (bottommost === -1) return 0;
    
    // Compute the height of the enclosing rectangle
    let height = bottommost - topmost + 1;
    
    // Compute the width of the enclosing rectangle
    let width = rightmost - leftmost + 1;
    
    // Return the area of the enclosing rectangle
    return height * width;
};

Time Complexity: O(m+n)

This approach efficiently finds the minimum bounding rectangle enclosing all 1s using just one pass over the grid. Below is the detailed breakdown:

Finding the Boundaries (Single Scan of Grid)

We iterate through the entire grid once to determine the topmost, bottommost, leftmost, and rightmost indices of '1's.

Iterating over each row and column:
→Outer loop (iterating through rows) → O(n)
→ Inner loop (iterating through columns) → O(m)
Since we scan the grid only once, the total time complexity for finding the boundaries is O(n × m)

Computing the Area
Once the boundary indices are found, we compute the area using:
Area=(bottommost−topmost+1)×(rightmost−leftmost+1)
This calculation involves basic arithmetic operations, which run in O(1) time.

Overall Time Complexity: O(n×m)+O(1)=O(n×m)

Since we only perform a single scan of the grid and a constant-time computation, this is the most optimal approach possible.

Space Complexity: O(n*m)

Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.

  • We use only a few integer variables (topmost, bottommost, leftmost, rightmost) to track boundaries.
  • No additional data structures (like arrays, stacks, or hash maps) are used.
  • Thus, the auxiliary space complexity is O(1).

Total Space Complexity

  • The input grid itself takes O(n × m) space, where n is the number of rows and m is the number of columns.
  • Since we do not create any additional data structures beyond the input grid, the overall space complexity remains O(n × m).

Final Space Complexity: O(n × m)

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.