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 II

Number: 3459

Difficulty: Hard

Paid? No

Companies: Salesforce

Problem Description

Given a 2D binary grid, we must cover every cell that contains a 1 using exactly three rectangles. Each rectangle must have a non‐zero area with horizontal and vertical sides, and the three rectangles must be pairwise non overlapping (although they may touch). Our task is to return the minimum possible sum of the areas of these three rectangles.

Key Insights

  • Since the rectangles must be non overlapping and cover all 1’s, an optimal solution will “tightly” cover separated groups of ones.
  • Due to non overlapping requirement, the rectangles’ placements are “ordered” either along rows or columns, or by a combination of horizontal and vertical splits.
  • One can break the problem into different partitioning schemes. Typical schemes include: • Partitioning the grid into three horizontal stripes. • Partitioning the grid into three vertical stripes. • A mixed partition: for example, splitting the grid horizontally (top and bottom parts) and then splitting one block vertically.
  • For each candidate partition, the minimal covering rectangle for a group is simply the smallest bounding box that encloses all ones in that block.
  • Because grid dimensions are small (at most 30×30), we can afford to enumerate over all possible partition lines (both horizontal and vertical) and choose the best partition yielding the minimum area sum.

Space and Time Complexity

Time Complexity: O(m^3 * n + n^3 * m) in the worst-case, where m and n are the number of rows and columns respectively. This stems from enumerating over possible partition positions and computing bounding boxes. Space Complexity: O(1) extra space (aside from the input and constant-size variables used for enumeration).

Solution

We can solve the problem by “guessing” the ways to partition the grid into three non overlapping regions. The key steps are:

  1. Precompute helper functions that, given a block of rows (and/or columns), compute the smallest bounding rectangle that covers all ones within that block. If no ones exist in that block, continue (since every rectangle must have at least one 1 to ensure a nonzero area covering usage).
  2. Enumerate candidate partitions:
    • Horizontal stripes: choose two splits (row indices) that break the grid into three contiguous row intervals. For each interval, compute the minimal bounding rectangle covering the ones.
    • Vertical stripes: similarly, choose two column splits.
    • Mixed splits: for example, split the grid horizontally into a top and bottom part. Then further split the top part vertically into two non overlapping parts (or do the reverse: vertical then horizontal in one half). The idea is that among these schemes all possible “relative positions” of the three disjoint rectangles are covered.
  3. For each valid partition (where each block has at least one 1), calculate the area of its bounding rectangle (area = (height * width)) and update the answer with the sum if it is smaller than the current best.
  4. Return the minimal total area obtained.

A couple of important implementation notes:

  • Always recalc the bounding box (min and max row and column) for the ones that fall into a given block.
  • Ensure that rectangles are valid (non-zero area) – the blocks that have ones must produce a bounding rectangle with positive area.
  • Take care when two partitions “touch”. Touching is allowed, but overlapping is not.

Below are code solutions in Python, JavaScript, C++ and Java with inline comments.

Code Solutions

# Python solution outline
def findMinArea(grid):
    m, n = len(grid), len(grid[0])
    INF = float("inf")
    # Helper: Get bounding box area for ones in a subgrid defined by row [r1, r2] and col [c1, c2].
    def get_area(r1, c1, r2, c2):
        min_r, max_r = m, -1
        min_c, max_c = n, -1
        for i in range(r1, r2+1):
            for j in range(c1, c2+1):
                if grid[i][j] == 1:
                    min_r = min(min_r, i)
                    max_r = max(max_r, i)
                    min_c = min(min_c, j)
                    max_c = max(max_c, j)
        # If no ones found, return 0 so that partition can be skipped.
        if max_r == -1:
            return 0
        # Since rectangle area must be nonzero and must cover all ones
        return (max_r - min_r + 1) * (max_c - min_c + 1)
    
    result = INF

    # Case 1: Three horizontal stripes.
    # Two splits: first stripe rows [0, i], second [i+1, j], third [j+1, m-1]
    for i in range(m-2):
        for j in range(i+1, m-1):
            area1 = get_area(0, 0, i, n-1)
            area2 = get_area(i+1, 0, j, n-1)
            area3 = get_area(j+1, 0, m-1, n-1)
            # Only consider if every stripe contains a one.
            if area1 and area2 and area3:
                result = min(result, area1 + area2 + area3)

    # Case 2: Three vertical stripes.
    # Two splits: first stripe cols [0, i], second [i+1, j], third [j+1, n-1]
    for i in range(n-2):
        for j in range(i+1, n-1):
            area1 = get_area(0, 0, m-1, i)
            area2 = get_area(0, i+1, m-1, j)
            area3 = get_area(0, j+1, m-1, n-1)
            if area1 and area2 and area3:
                result = min(result, area1 + area2 + area3)

    # Case 3: Mixed split – horizontal then vertical split in the top part.
    # Split horizontally: top block rows [0, x], bottom block rows [x+1, m-1]
    for x in range(m-1):
        # In top block, try a vertical split at column y.
        for y in range(n-1):
            top_left = get_area(0, 0, x, y)
            top_right = get_area(0, y+1, x, n-1)
            bottom = get_area(x+1, 0, m-1, n-1)
            if top_left and top_right and bottom:
                result = min(result, top_left + top_right + bottom)
    # Also consider the mirror: vertical then horizontal split in the left part.
    for y in range(n-1):
        for x in range(m-1):
            left_top = get_area(0, 0, x, y)
            left_bottom = get_area(x+1, 0, m-1, y)
            right = get_area(0, y+1, m-1, n-1)
            if left_top and left_bottom and right:
                result = min(result, left_top + left_bottom + right)

    return result if result != INF else -1

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