Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Inside a chosen region, the smallest rectangle covering its ones is their bounding box. The challenge is separating the ones into three regions. Three disjoint axis-aligned rectangles admit a horizontal or vertical cut separating one rectangle from the other two; a second cut separates that pair. This yields parallel strips or a T-shaped partition.

Approach

Use a helper that scans a region and returns the area of its ones' bounding box. With the supplied sentinel coordinates, a region containing no ones receives a very large cost and cannot improve a valid answer.

Enumerate three horizontal strips, and both arrangements where a horizontal cut separates one full-width region from two side-by-side regions. For each partition, sum the three helper results. Rotate the grid by 90 degrees and repeat to cover vertical strips and the other T-shaped orientations. Return the minimum cost.

The problem guarantees at least three ones. An optimal covering can use three rectangles each containing a one: an otherwise unused rectangle can instead split a rectangle covering multiple ones without increasing the total area. Thus excluding empty groups does not lose an optimum.

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        def area(t, b, l, r):
            top = 100000
            bottom = -1
            left = 100000
            right = -1

            for i in range(t, b + 1):
                for j in range(l, r + 1):
                    if grid[i][j] == 1:
                        top = min(top, i)
                        bottom = max(bottom, i)
                        left = min(left, j)
                        right = max(right, j)

            return (bottom - top + 1) * (right - left + 1)

        def solve():
            res = float('inf')
            n = len(grid)
            m = len(grid[0])

            for i in range(n):
                for j in range(m):
                    res = min(
                        res,
                        area(0, i, 0, j) + area(0, i, j + 1, m - 1) + area(i + 1, n - 1, 0, m - 1)
                    )
                    res = min(
                        res,
                        area(0, i, 0, m - 1) + area(i + 1, n - 1, 0, j) + area(i + 1, n - 1, j + 1, m - 1)
                    )

            for i in range(n - 1):
                for j in range(i + 1, n - 1):
                    res = min(
                        res,
                        area(0, i, 0, m - 1) + area(i + 1, j, 0, m - 1) + area(j + 1, n - 1, 0, m - 1)
                    )

            return res

        out = solve()
        n = len(grid)
        m = len(grid[0])
        new_grid = [[0] * n for _ in range(m)]

        for i in range(n):
            for j in range(m):
                new_grid[j][n - 1 - i] = grid[i][j]

        grid = new_grid
        return min(out, solve())

Complexity analysis

Let r and c be the grid dimensions. Time: O(r * c * (r * c + r^2 + c^2)) for all partition candidates and their rescans. Auxiliary space: O(r * c) for the rotated grid and DP-free working storage.