3197. Find the Minimum Area to Cover All Ones II
Hard
50 Points
Array
Matrix
Enumeration
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
Input: grid = [[1,0,1],[1,1,1]]
Output: 5
Explanation:
Example 2
Input: grid = [[1,0,1,0],[0,1,0,1]]
Output: 5
Explanation:
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.
3197. Find the Minimum Area to Cover All Ones II
Hard
50 Points
Array
Matrix
Enumeration
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
Input: grid = [[1,0,1],[1,1,1]]
Output: 5
Explanation:
Example 2
Input: grid = [[1,0,1,0],[0,1,0,1]]
Output: 5
Explanation:
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.