Package g3101_3200.s3197_find_the_minimum_area_to_cover_all_ones_ii

Class Solution

java.lang.Object
g3101_3200.s3197_find_the_minimum_area_to_cover_all_ones_ii.Solution
public class Solution extends java.lang.Object
3197 - 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.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Solution()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    minimumSum(int[][] grid)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • minimumSum

      public int minimumSum(int[][] grid)