diff options
Diffstat (limited to 'find_min_area_conver_ones2.py')
-rw-r--r-- | find_min_area_conver_ones2.py | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/find_min_area_conver_ones2.py b/find_min_area_conver_ones2.py new file mode 100644 index 0000000..c61d18d --- /dev/null +++ b/find_min_area_conver_ones2.py @@ -0,0 +1,62 @@ +# 3197. Find the Minimum Area to Cover All Ones II + +""" +you are giiven 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 the 'grid' lie inside these rectangles. return the minimum +possible sum of the area of these rectangles. note that the rectangles are +allowed to touch. +""" + + +class Solution(object): + def min_area(self, grid): + if not grid or not grid[0]: + return 0 + n, m = len(grid), len(grid[0]) + left, top, right, bottom = float("inf"), float("inf"), -1, -1 + for i in range(n): + for j in range(m): + if grid[i][j] == 1: + left = min(left, j) + top = min(top, i) + right = max(right, j) + bottom = max(bottom, i) + if right == -1: + return 0 + return (right - left + 1) * (bottom - top + 1) + + def rotate(self, grid): + n, m = len(grid), len(grid[0]) + return [[grid[i][j] for i in range(n - 1, -1, -1)] for j in range(m)] + + def minimumSum(self, grid): + """ + :type grid: List[List[int]] + :rtype: int + """ + ans = float("inf") + for _ in range(4): + n, m = len(grid), len(grid[0]) + for i in range(1, n): + a1 = self.min_area(grid[:i]) + for j in range(1, m): + p2 = [row[:j] for row in grid[i:]] + p3 = [row[j:] for row in grid[i:]] + a2 = self.min_area(p2) + a3 = self.min_area(p3) + ans = min(ans, a1 + a2 + a3) + for i2 in range(i + 1, n): + p2 = grid[i:i2] + p3 = grid[i2:] + a2 = self.min_area(p2) + a3 = self.min_area(p3) + ans = min(ans, a1 + a2 + a3) + grid = self.rotate(grid) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumSum(grid=[[1, 0, 1], [1, 1, 1]])) + print(obj.minimumSum(grid=[[1, 0, 1, 0], [0, 1, 0, 1]])) |