Skip to content

3459. Find The Minimum Area To Cover All Ones II

Array Matrix Enumeration

Problem - Find The Minimum Area To Cover All Ones II

Hard

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.

 

Example 1:

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

Output: 5

Explanation:

  • 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:

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

Output: 5

Explanation:

  • 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.

Solutions

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        def calc(i1: int, j1: int, i2: int, j2: int) -> int:
            x1 = y1 = inf
            x2 = y2 = -inf
            for i in range(i1, i2 + 1):
                for j in range(j1, j2 + 1):
                    if grid[i][j] == 1:
                        x1 = min(x1, i)
                        x2 = max(x2, i)
                        y1 = min(y1, j)
                        y2 = max(y2, j)

            return (y2 - y1 + 1) * (x2 - x1 + 1)

        m, n = len(grid), len(grid[0])
        result = m * n

        for i1 in range(m - 1):
            for i2 in range(i1 + 1, m - 1):
                result = min(result,
                    calc(0, 0, i1, n - 1)
                    + calc(i1 + 1, 0, i2, n - 1)
                    + calc(i2 + 1, 0, m - 1, n - 1)
                )

        for j1 in range(n - 1):
            for j2 in range(j1 + 1, n - 1):
                result = min(result,
                    calc(0, 0, m - 1, j1)
                    + calc(0, j1 + 1, m - 1, j2)
                    + calc(0, j2 + 1, m - 1, n - 1)
                )

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

                result = min(
                    result,
                    calc(0, 0, i, j) + calc(i + 1, 0, m - 1, j) + calc(0, j + 1, m - 1, n - 1),
                )
                result = min(
                    result,
                    calc(0, 0, m - 1, j)
                    + calc(0, j + 1, i, n - 1)
                    + calc(i + 1, j + 1, m - 1, n - 1),
                )
        return result

Submission Stats:

  • Runtime: 6416 ms (19.04%)
  • Memory: 17.9 MB (66.96%)