diff options
Diffstat (limited to 'largest_submatrix.c')
-rw-r--r-- | largest_submatrix.c | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/largest_submatrix.c b/largest_submatrix.c new file mode 100644 index 0000000..4caa160 --- /dev/null +++ b/largest_submatrix.c @@ -0,0 +1,35 @@ +// 1727. Largest Submatrix With Rearrangements +#include "leetcode.h" + +/* + * you are given a binary matrix of size 'm * n' and you are allowed to + * rearrange the columns of the 'matrix' in any order. return the area of the + * largest submatrix within 'matrix' where every element of the submatrix is 1 + * after reordering columns optimally + */ + +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } + +int largestSubmatrix(int **matrix, int matrix_size, int *matrix_col_size) { + int **heights = (int **)malloc(matrix_size * sizeof(int *)), max_area = 0; + for (int i = 0; i < matrix_size; i++) { + heights[i] = (int *)malloc(*matrix_col_size * sizeof(int)); + for (int j = 0; j < *matrix_col_size; j++) { + if (!i) + heights[i][j] = matrix[i][j]; + else + heights[i][j] = (matrix[i][j] == 1) ? heights[i - 1][j] + 1 : 0; + } + } + for (int i = 0; i < matrix_size; i++) { + qsort(heights[i], *matrix_col_size, sizeof(int), cmp); + for (int j = 0; j < *matrix_col_size; j++) { + int width = *matrix_col_size - j, height = heights[i][j]; + max_area = fmax(max_area, width * height); + } + } + for (int i = 0; i < matrix_size; i++) + free(heights[i]); + free(heights); + return max_area; +} |