Watch 10 video solutions for Find the Minimum Area to Cover All Ones II, a hard level problem involving Array, Matrix, Enumeration. This walkthrough by codestorywithMIK has 8,854 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
(0, 0) and (1, 0) are covered by a rectangle of area 2.(0, 2) and (1, 2) are covered by a rectangle of area 2.(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:
(0, 0) and (0, 2) are covered by a rectangle of area 3.(1, 1) is covered by a rectangle of area 1.(1, 3) is covered by a rectangle of area 1.
Constraints:
1 <= grid.length, grid[i].length <= 30grid[i][j] is either 0 or 1.grid.Problem Overview: You are given a binary grid and must cover every cell containing 1 using exactly three axis-aligned rectangles. Rectangles cannot overlap in a way that changes the counted area, and the goal is to minimize the total covered area. Each rectangle may include extra 0 cells, but every 1 must lie inside one of the chosen rectangles.
Approach 1: Brute Force and Combinatorial Splitting (High Polynomial Time, ~O(m^2 * n^2))
The direct strategy enumerates all ways to split the grid into three regions using horizontal and vertical cuts. For each partition configuration, compute the bounding box of 1s inside each region and calculate its rectangle area. The total area is the sum of the three bounding boxes. You iterate through combinations such as three horizontal strips, three vertical strips, or mixed L-shaped partitions created by one horizontal and one vertical cut. This approach works because the grid is small enough that all structural partitions can be explored exhaustively.
Approach 2: Bitmask and Dynamic Programming (O(m * n * 2^k) style state exploration)
This approach models assignment of cells or subregions to one of three rectangles using bitmasks. Precompute bounding boxes for subsets or incremental states, then use dynamic programming to track the minimum area for covering discovered 1 cells with up to three rectangles. Bitmasks represent which rectangles are already used or which partitions are active. It reduces repeated recomputation when exploring different configurations and is easier to implement in languages with fast bit operations.
Approach 3: Dynamic Programming over Grid Partitions (≈O(m^2 * n^2))
Dynamic programming improves the brute-force idea by caching results for submatrices. Precompute prefix information so you can quickly determine the bounding box of 1s inside any submatrix. Then evaluate transitions where the grid is split horizontally or vertically and distribute the three rectangles among the resulting regions. Because subproblems repeat across different partition structures, memoization significantly reduces redundant calculations.
Approach 4: Backtracking Enumeration
Backtracking explicitly constructs rectangles by expanding boundaries around groups of 1s. At each step you choose a region that covers some remaining cells and recursively place the next rectangle. Pruning happens when the current accumulated area already exceeds the best known answer. This approach is flexible but requires careful pruning to remain practical.
Recommended for interviews: The partition-enumeration or dynamic programming solution is typically expected. Interviewers want to see that you recognize the grid can be divided into three rectangles using structured horizontal and vertical splits. Starting with brute-force partitioning shows understanding of the geometry, while optimizing with prefix computations or memoization demonstrates strong matrix and enumeration skills. The problem also relies on careful iteration across a 2D array grid.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Combinatorial Splitting | O(m^2 * n^2) | O(1) | When grid size is small and you want the simplest implementation by enumerating all partition structures |
| Bitmask + Dynamic Programming | O(m * n * 2^k) | O(2^k) | When exploring rectangle assignments and reusing computed states across configurations |
| Dynamic Programming on Grid Partitions | O(m^2 * n^2) | O(m * n) | General optimized solution using cached results for submatrices |
| Backtracking with Pruning | Exponential (pruned) | O(recursion depth) | Useful for experimentation or when strong pruning rules limit the search space |