From 35df6818e96a1bd2db2a7aca00224ff39e1b8f13 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Thu, 21 Aug 2025 21:28:19 -0600 Subject: 3195. find the minimum area to cover all ones 1 --- find_min_area_conver_ones1.c | 38 ++++++++++++++++++++++++++++++++++++++ find_min_area_conver_ones1.py | 32 ++++++++++++++++++++++++++++++++ 2 files changed, 70 insertions(+) create mode 100644 find_min_area_conver_ones1.c create mode 100644 find_min_area_conver_ones1.py diff --git a/find_min_area_conver_ones1.c b/find_min_area_conver_ones1.c new file mode 100644 index 0000000..3dc66be --- /dev/null +++ b/find_min_area_conver_ones1.c @@ -0,0 +1,38 @@ +// 3195. Find the Minimum Area to Cover All Ones I +#include "leetcode.h" + +/* + * you are given a 2d binary array 'grid'. find a rectangle with horizontal and + * vertical lines with the smallest area, such that all the 1's in 'grid' lie + * inside this rectangle. return the minimum possible area of the rectangle. + */ + +int minimumArea(int **grid, int gridSize, int *gridColSize) { + int m = gridSize, n = gridColSize[0]; + int min_row = m, max_row = -1; + int min_col = n, max_col = -1; + for (int i = 0; i < m; i++) + for (int j = 0; j < n; j++) + if (grid[i][j]) { + if (i < min_row) + min_row = i; + if (i > max_row) + max_row = i; + if (j < min_col) + min_col = j; + if (j > max_col) + max_col = j; + } + return (max_row - min_row + 1) * (max_col - min_col + 1); +} + +int main() { + int g1i[2][3] = {{0, 1, 0}, {1, 0, 1}}, g2i[2][2] = {{1, 0}, {0, 0}}; + 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", minimumArea(g1.arr, g1.row_size, g1.col_size)); // expect: 6 + printf("%d\n", minimumArea(g2.arr, g2.row_size, g2.col_size)); // expect: 1 + two_d_arr_free(&g1); + two_d_arr_free(&g2); +} diff --git a/find_min_area_conver_ones1.py b/find_min_area_conver_ones1.py new file mode 100644 index 0000000..9374874 --- /dev/null +++ b/find_min_area_conver_ones1.py @@ -0,0 +1,32 @@ +# 3195. Find the Minimum Area to Cover All Ones I + +""" +you are given a 2d binary array 'grid'. find a rectangle with horizontal and +vertical lines with the smallest area, such that all the 1's in 'grid' lie +inside this rectangle. return the minimum possible area of the rectangle. +""" + + +class Solution: + def minimumArea(self, grid): + """ + :type grid: List[List[int]] + :rtype: int + """ + m, n = len(grid), len(grid[0]) + min_row, max_row = m, -1 + min_col, max_col = n, -1 + for i in range(m): + for j in range(n): + if grid[i][j] == 1: + min_row = min(min_row, i) + max_row = max(max_row, i) + min_col = min(min_col, j) + max_col = max(max_col, j) + return (max_row - min_row + 1) * (max_col - min_col + 1) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumArea(grid=[[0, 1, 0], [1, 0, 1]])) + print(obj.minimumArea(grid=[[1, 0], [0, 0]])) -- cgit v1.2.3