Find the Minimum Area to Cover All Ones II - Solution & Explanation
Problem Statement
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 <= 30grid[i][j]is either 0 or 1.- The input is generated such that there are at least three 1's in
grid.
Approach Overview
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 1: Brute Force and Combinatorial Splitting
This approach involves identifying all positions of '1' in the grid and using combinatorial methods to select groups of these positions to form the smallest possible set of three non-overlapping rectangles.
The process involves:
- Enumerating all positions containing '1'.
- Trying all possible ways of assigning positions of '1' to three rectangles, ensuring each rectangle is non-overlapping and has a non-zero area.
- Evaluating each assignment to calculate the total area of the rectangles formed and keeping track of the minimum found.
This solution uses the brute force method to try every possible way of grouping the ones in the grid into three separate rectangles. The key steps involve iterating over every subset of the available ones, attempting to split them into non-overlapping sets representing the rectangles.
The function calculates areas for each rectangle set if they cover all the 1s while minimizing this value.
Code
Python
Complexity
Time Complexity: O(2^n * 2^n), where n is the number of '1's, which is feasible due to n ≤ 30.
Space Complexity: O(n) for storing coordinates of the '1's and subsets.
Approach 2: Bitmask and Dynamic Programming
This approach focuses on using dynamic programming, coupled with bitmasking, to efficiently partition the 1s into three separate rectangles with minimal sums.
The implementation details are:
- Use a bitmask to represent which rectangle a particular '1' in the grid belongs to (there are three potential groups).
- Compute minimum area sums using dynamic programming by leveraging the overlap and inclusion-exclusion properties of bitmasks and set assignments.
This solution involves the combination of dynamic programming and bitmasking to efficiently compute the minimal area. It calculates rectangular bounds iteratively through the combination of assigning subsets through masks.
Each loop attempts to mask subsets and gather calculations with respect to non-overlapping constraints and minimum areas through partitioning.
Code
JavaScript
Complexity
Time Complexity: O(3^n), where n is the number of '1's, leveraging bitmasking for dynamic assignment representation.
Space Complexity: O(3^n) due to space needed for storing dynamic state transitions and expressions.
Approach 3: Dynamic Programming Approach
This approach uses dynamic programming to explore different ways of selecting rectangles. We can use a 3D dp array where dp[i][j][k] keeps track of the minimum area to cover the 1's in the grid using up to k rectangles, covering 1's from position 0 to i and 0 to j. The approach involves iterating over possible areas and choosing optimal rectangles.
This C implementation demonstrates the use of dynamic programming to solve the problem....
Complexity
Time Complexity: O(n^3)
Space Complexity: O(n^3)
Approach 4: Backtracking Approach
In this approach, we use backtracking to explore all possible ways of selecting rectangles. The idea is to backtrack by selecting a starting point for three rectangles and expand each one to cover 1's and then compute the area.
This C solution uses backtracking techniques to find potential rectangles...
Complexity
Time Complexity: Exponential
Space Complexity: O(n^2)
Approach 5: Enumeration
According to the problem description, we can use two dividing lines to split the rectangle into three parts. We calculate the minimum rectangular area containing all 1s for each part and then take the minimum sum of the areas of the three parts.
We can enumerate the positions of the two dividing lines, which have 6 possibilities:
- Two horizontal splits
- Two vertical splits
- First perform a horizontal split, then a vertical split on the upper part
- First perform a horizontal split, then a vertical split on the lower part
- First perform a vertical split, then a horizontal split on the left part
- First perform a vertical split, then a horizontal split on the right part
We can use a function f(i_1, j_1, i_2, j_2) to calculate the minimum rectangular area containing all 1s from (i_1, j_1) to (i_2, j_2).
The time complexity is O(m^2 times n^2), where m and n are the number of rows and columns of the rectangle, respectively. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force and Combinatorial Splitting | Time Complexity: O(2^n * 2^n), where n is the number of '1's, which is feasible due to n ≤ 30. Space Complexity: O(n) for storing coordinates of the '1's and subsets. |
| Bitmask and Dynamic Programming | Time Complexity: O(3^n), where n is the number of '1's, leveraging bitmasking for dynamic assignment representation. Space Complexity: O(3^n) due to space needed for storing dynamic state transitions and expressions. |
| Dynamic Programming Approach | Time Complexity: O(n^3) Space Complexity: O(n^3) |
| Backtracking Approach | Time Complexity: Exponential Space Complexity: O(n^2) |
| Enumeration | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Find the Minimum Area to Cover All Ones II | Detailed Explanation | Leetcode 3197 | codestorywithMIK • codestorywithMIK • 8,976 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Minimum Area to Cover All Ones II easy or hard?
Find the Minimum Area to Cover All Ones II Python/Java solution
How to solve Find the Minimum Area to Cover All Ones II in O(n)?
What is the best approach for Find the Minimum Area to Cover All Ones II?
Is Find the Minimum Area to Cover All Ones II asked at Google/Amazon/Meta?
What data structure is used in Find the Minimum Area to Cover All Ones II?
What is the time complexity of Find the Minimum Area to Cover All Ones II?
Ready to solve this problem?
Practice Find the Minimum Area to Cover All Ones II with our built-in code editor and test cases.
Practice on FleetCode