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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Minimum Area to Cover All Ones I

Difficulty: Medium

Problem Description

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.

Key Insights

  • To determine the smallest rectangle covering all ones, we need to find the minimum and maximum row and column indices that contain a 1.
  • The area of the rectangle can be computed using the formula: (max_row - min_row + 1) * (max_col - min_col + 1).
  • The algorithm requires iterating through the grid to locate the boundaries of the rectangle.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of rows and m is the number of columns in the grid.
Space Complexity: O(1), as we only use a fixed amount of extra space for variables.

Solution

To solve the problem, we can follow these steps:

  1. Initialize variables to track the minimum and maximum row and column indices of the 1's found in the grid.
  2. Iterate through each cell in the grid:
    • If a cell contains a 1, update the min and max row and column indices accordingly.
  3. Once we have the boundaries, calculate the area of the rectangle using the previously mentioned formula.

Code Solutions

def minArea(grid):
    rows, cols = len(grid), len(grid[0])
    min_row, max_row, min_col, max_col = rows, -1, cols, -1

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                min_row = min(min_row, r)
                max_row = max(max_row, r)
                min_col = min(min_col, c)
                max_col = max(max_col, c)

    return (max_row - min_row + 1) * (max_col - min_col + 1)
← Back to All Questions