We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Minimum Area to Cover All Ones I

Number: 3461

Difficulty: Medium

Paid? No

Companies: Salesforce

Problem Description

You are given a 2D binary array grid. The task is to find the rectangle (with horizontal and vertical sides) that covers all the 1's in the grid with the smallest possible area. In other words, determine the minimum area rectangle that encloses every 1 present in grid.

Key Insights

  • The solution requires identifying the extreme boundaries (topmost, bottommost, leftmost, and rightmost positions) where a 1 occurs.
  • Iterating through the grid once is sufficient to determine these boundaries.
  • Once the boundaries are identified, compute the rectangle's area using (max_row - min_row + 1) * (max_col - min_col + 1).

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns, since we traverse each element once. Space Complexity: O(1) aside from the input grid.

Solution

The approach involves scanning each cell in the grid to update boundary variables:

  1. Initialize min_row to the number of rows and max_row to -1.
  2. Initialize min_col to the number of columns and max_col to -1.
  3. For every cell that contains a 1, update the variables accordingly.
  4. After processing the entire grid, compute the area with the formula (max_row - min_row + 1) * (max_col - min_col + 1).

This simple and efficient method ensures all ones are enclosed by the rectangle with minimal area.

Code Solutions

def minArea(grid):
    # Get the dimensions of the grid
    m = len(grid)
    n = len(grid[0])
    
    # Initialize boundaries for rows and columns
    min_row, max_row = m, -1
    min_col, max_col = n, -1
    
    # Traverse the grid
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                # Update the boundary positions
                min_row = min(min_row, i)
                max_row = max(max_row, i)
                min_col = min(min_col, j)
                max_col = max(max_col, j)
    
    # Compute the area of the rectangle covering all ones
    return (max_row - min_row + 1) * (max_col - min_col + 1)

# Example usage:
# grid = [[0,1,0],[1,0,1]]
# print(minArea(grid))  # Output: 6
← Back to All Questions