aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-23 19:35:04 -0600
committerJack Sangdahl <[email protected]>2025-08-23 19:35:04 -0600
commit199f44e965e130cdd50a59163168f7ba448457dd (patch)
treec7033c55072a3a775a77fce7e71bb00886d0c891
parentc52a5472ea66ab8b216d3fa26fe643525629af3d (diff)
downloadleetcode-199f44e965e130cdd50a59163168f7ba448457dd.tar.gz
leetcode-199f44e965e130cdd50a59163168f7ba448457dd.zip
3197. find the minimum area to cover all ones 2
-rw-r--r--find_min_area_conver_ones2.c84
-rw-r--r--find_min_area_conver_ones2.py62
2 files changed, 146 insertions, 0 deletions
diff --git a/find_min_area_conver_ones2.c b/find_min_area_conver_ones2.c
new file mode 100644
index 0000000..503820c
--- /dev/null
+++ b/find_min_area_conver_ones2.c
@@ -0,0 +1,84 @@
+// 3197. Find the Minimum Area to Cover All Ones II
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+int min_area(int **grid, int gridSize, int gridColSize) {
+ int left = 1e9, top = 1e9, right = -1, bottom = -1;
+ for (int i = 0; i < gridSize; i++) {
+ for (int j = 0; j < gridColSize; j++) {
+ if (grid[i][j] == 1) {
+ if (j < left)
+ left = j;
+ if (i < top)
+ top = i;
+ if (j > right)
+ right = j;
+ if (i > bottom)
+ bottom = i;
+ }
+ }
+ }
+ if (right == -1)
+ return 0;
+ return (right - left + 1) * (bottom - top + 1);
+}
+
+int **rotate(int **grid, int gridSize, int gridColSize) {
+ int **res = (int **)malloc(gridColSize * sizeof(int *));
+ for (int i = 0; i < gridColSize; i++)
+ res[i] = (int *)malloc(gridSize * sizeof(int));
+ for (int i = 0; i < gridSize; i++)
+ for (int j = 0; j < gridColSize; j++)
+ res[j][gridSize - 1 - i] = grid[i][j];
+ return res;
+}
+
+int minimumSum(int **grid, int gridSize, int *gridColSize) {
+ int ans = 1e9;
+ for (int rot = 0; rot < 4; rot++) {
+ int m = gridColSize[0];
+ for (int i = 1; i < gridSize; i++) {
+ int a1 = min_area(grid, i, m);
+ for (int j = 1; j < m; j++) {
+ int **p2 = (int **)malloc((gridSize - i) * sizeof(int *));
+ int **p3 = (int **)malloc((gridSize - i) * sizeof(int *));
+ for (int r = 0; r < gridSize - i; r++) {
+ p2[r] = (int *)malloc(j * sizeof(int));
+ p3[r] = (int *)malloc((m - j) * sizeof(int));
+ for (int c = 0; c < j; c++)
+ p2[r][c] = grid[i + r][c];
+ for (int c = j; c < m; c++)
+ p3[r][c - j] = grid[i + r][c];
+ }
+ int a2 = min_area(p3, gridSize - i, j);
+ int a3 = min_area(p3, gridSize - i, m - j);
+ if (a1 + a2 + a3 < ans)
+ ans = a1 + a2 + a3;
+ }
+ }
+ grid = rotate(grid, gridSize, gridColSize[0]);
+ int tmp = gridSize;
+ gridSize = gridColSize[0];
+ gridColSize[0] = tmp;
+ }
+ return ans;
+}
+
+int main() {
+ int g1i[2][3] = {{1, 0, 1}, {1, 1, 1}},
+ g2i[2][4] = {{1, 0, 1, 0}, {0, 1, 0, 1}};
+ struct two_d_arr g1, g2;
+ two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ printf("%d\n", minimumSum(g1.arr, g1.row_size, g1.col_size)); // expect: 5
+ printf("%d\n", minimumSum(g2.arr, g2.row_size, g2.col_size)); // expect: 5
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+}
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]]))