aboutsummaryrefslogtreecommitdiff
path: root/largest_submatrix.c
diff options
context:
space:
mode:
Diffstat (limited to 'largest_submatrix.c')
-rw-r--r--largest_submatrix.c35
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;
+}