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 II

Difficulty: Hard

Problem Description

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.

Key Insights

  • The problem requires covering all the 1's in the grid using three rectangles.
  • The rectangles must be non-overlapping, but they can touch.
  • The objective is to minimize the total area covered by the rectangles.
  • The grid size is relatively small (maximum 30x30), allowing for exhaustive search techniques.

Space and Time Complexity

Time Complexity: O(N^3 * M^3), where N is the number of rows and M is the number of columns in the grid. This accounts for iterating through all possible rectangle placements. Space Complexity: O(1), as we only use a constant amount of additional space beyond the input grid.

Solution

The solution involves iterating over all possible combinations of three rectangles that can cover all the 1's in the grid. For each rectangle, we calculate its area and keep track of the minimum total area for valid combinations. The approach utilizes nested loops to select the top-left and bottom-right corners of each rectangle, ensuring that they don't overlap with each other. A set is used to track which 1's have already been covered by previously selected rectangles.

Code Solutions

def minArea(grid):
    rows, cols = len(grid), len(grid[0])
    ones = [(i, j) for i in range(rows) for j in range(cols) if grid[i][j] == 1]
    total_ones = len(ones)
    min_area_sum = float('inf')

    for i1 in range(total_ones):
        for j1 in range(i1 + 1, total_ones):
            for k1 in range(j1 + 1, total_ones):
                rects = [ones[i1], ones[j1], ones[k1]]
                area_sum = 0
                covered = set()

                for x1, y1 in rects:
                    x2, y2 = x1, y1
                    while x2 < rows and grid[x2][y1] == 1:
                        x2 += 1
                    while y2 < cols and grid[x1][y2] == 1:
                        y2 += 1
                    area = (x2 - x1) * (y2 - y1)

                    # Check if this rectangle covers new 1's
                    if not any((i, j) in covered for i in range(x1, x2) for j in range(y1, y2)):
                        area_sum += area
                        for i in range(x1, x2):
                            for j in range(y1, y2):
                                if grid[i][j] == 1:
                                    covered.add((i, j))

                if len(covered) == total_ones:
                    min_area_sum = min(min_area_sum, area_sum)

    return min_area_sum
← Back to All Questions