From 199f44e965e130cdd50a59163168f7ba448457dd Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 23 Aug 2025 19:35:04 -0600 Subject: 3197. find the minimum area to cover all ones 2 --- find_min_area_conver_ones2.py | 62 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) create mode 100644 find_min_area_conver_ones2.py (limited to 'find_min_area_conver_ones2.py') 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]])) -- cgit v1.2.3