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 Sahil & Sarra has 656,704 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.