Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: grid = [[1,0,1],[1,1,1]]

Output: 5

Explanation:

![](https://assets.leetcode.com/uploads/2024/05/14/example0rect21.png)

  * The 1's at `(0, 0)` and `(1, 0)` are covered by a rectangle of area 2.
  * The 1's at `(0, 2)` and `(1, 2)` are covered by a rectangle of area 2.
  * The 1 at `(1, 1)` is covered by a rectangle of area 1.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: grid = [[1,0,1,0],[0,1,0,1]]

Output: 5

Explanation:

![](https://assets.leetcode.com/uploads/2024/05/14/example1rect2.png)

  * The 1's at `(0, 0)` and `(0, 2)` are covered by a rectangle of area 3.
  * The 1 at `(1, 1)` is covered by a rectangle of area 1.
  * The 1 at `(1, 3)` is covered by a rectangle of area 1.

Constraints

  • 1 <= grid.length, grid[i].length <= 30
  • grid[i][j] is either 0 or 1.
  • The input is generated such that there are at least three 1’s in grid.

Solution

Method 1 – Brute Force All Rectangle Partitions (for Small Grids)

Intuition

We need to cover all 1’s in the grid with 3 non-overlapping rectangles of non-zero area, minimizing the total area. For small grids, we can brute-force all possible ways to partition the grid into 3 rectangles, check if all 1’s are covered, and compute the minimum area sum.

Approach

  1. For each possible way to split the grid into 3 rectangles (by vertical and/or horizontal cuts), enumerate all possible rectangles.
  2. For each combination of 3 rectangles, check:
    • All rectangles have non-zero area.
    • Rectangles do not overlap.
    • All 1’s in the grid are covered by at least one rectangle.
  3. Compute the sum of the areas for valid combinations and track the minimum.
  4. Return the minimum area sum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution:
    def minArea(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ones = [(i,j) for i in range(m) for j in range(n) if grid[i][j]==1]
        if not ones:
            return 0
        ans = float('inf')
        # Try all possible rectangles for the first
        for r1 in range(m):
            for r2 in range(r1, m):
                for c1 in range(n):
                    for c2 in range(c1, n):
                        rect1 = set((i,j) for i in range(r1,r2+1) for j in range(c1,c2+1))
                        if not any((i,j) in rect1 for (i,j) in ones):
                            continue
                        # Try all possible rectangles for the second
                        for rr1 in range(m):
                            for rr2 in range(rr1, m):
                                for cc1 in range(n):
                                    for cc2 in range(cc1, n):
                                        rect2 = set((i,j) for i in range(rr1,rr2+1) for j in range(cc1,cc2+1))
                                        if rect1 & rect2:
                                            continue
                                        if not any((i,j) in rect2 for (i,j) in ones):
                                            continue
                                        # Third rectangle covers the rest
                                        covered = rect1 | rect2
                                        left = [p for p in ones if p not in covered]
                                        if not left:
                                            continue
                                        minr = min(i for i,j in left)
                                        maxr = max(i for i,j in left)
                                        minc = min(j for i,j in left)
                                        maxc = max(j for i,j in left)
                                        area3 = (maxr-minr+1)*(maxc-minc+1)
                                        area1 = (r2-r1+1)*(c2-c1+1)
                                        area2 = (rr2-rr1+1)*(cc2-cc1+1)
                                        total = area1+area2+area3
                                        ans = min(ans, total)
        return ans if ans!=float('inf') else 0

Complexity

  • ⏰ Time complexity: O((m^2 n^2)^2), feasible only for very small grids (e.g., m,n <= 6).
  • 🧺 Space complexity: O(mn), for storing rectangles and positions.