leetcode

commit 2377266adb39dd1364db00342b1d317b79dbed60
parent c41c6f3448287f1a9db53c866f67ce7bce59b5a3
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 16 Mar 2026 21:08:05 -0600

1727. largest submatrix with rearrangements

Diffstat:
M
largest_submatrix.c
 | 
55
++++++++++++++++++++++++++++++++++++++-----------------
A
largest_submatrix.py
 | 
32
++++++++++++++++++++++++++++++++

2 files changed, 70 insertions(+), 17 deletions(-)
diff --git a/largest_submatrix.c b/largest_submatrix.c
@@ -10,26 +10,47 @@
 
 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++) {
+int largestSubmatrix(int **matrix, int matrixSize, int *matrixColSize) {
+  int m = matrixSize, n = matrixColSize[0];
+  int **hist = (int **)malloc(m * sizeof(int *));
+  for (int i = 0; i < m; ++i) {
+    hist[i] = (int *)malloc(n * sizeof(int));
+    for (int j = 0; j < n; ++j) {
       if (!i)
-        heights[i][j] = matrix[i][j];
+        hist[i][j] = matrix[i][j];
       else
-        heights[i][j] = (matrix[i][j] == 1) ? heights[i - 1][j] + 1 : 0;
+        hist[i][j] = !matrix[i][j] ? 0 : hist[i - 1][j] + 1;
     }
   }
-  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);
-    }
+  int ans = 0;
+  for (int i = 0; i < m; ++i) {
+    qsort(hist[i], n, sizeof(int), cmp);
+    for (int j = 0; j < n; ++j)
+      ans = fmax(ans, hist[i][j] * (n - j));
   }
-  for (int i = 0; i < matrix_size; i++)
-    free(heights[i]);
-  free(heights);
-  return max_area;
+  for (int i = 0; i < m; ++i)
+    free(hist[i]);
+  free(hist);
+  return ans;
+}
+
+int main() {
+  int m1i[3][3] = {{0, 0, 1}, {1, 1, 1}, {1, 0, 1}};
+  int m2i[1][5] = {{1, 0, 1, 0, 1}};
+  int m3i[2][3] = {{1, 1, 0}, {1, 0, 1}};
+  struct two_d_arr *m1 =
+      two_d_arr_init(ARRAY_SIZE(m1i), ARRAY_SIZE(m1i[0]), m1i);
+  struct two_d_arr *m2 =
+      two_d_arr_init(ARRAY_SIZE(m2i), ARRAY_SIZE(m2i[0]), m2i);
+  struct two_d_arr *m3 =
+      two_d_arr_init(ARRAY_SIZE(m3i), ARRAY_SIZE(m3i[0]), m3i);
+  int r1 = largestSubmatrix(m1->arr, m1->row_size, m1->col_size);
+  int r2 = largestSubmatrix(m2->arr, m2->row_size, m2->col_size);
+  int r3 = largestSubmatrix(m3->arr, m3->row_size, m3->col_size);
+  printf("%d\n", r1);
+  assert(r1 == 4);
+  printf("%d\n", r3);
+  assert(r2 == 3);
+  printf("%d\n", r3);
+  assert(r3 == 2);
 }
diff --git a/largest_submatrix.py b/largest_submatrix.py
@@ -0,0 +1,32 @@
+# 1727. Largest Submatrix With Rearrangements
+from typing import List
+
+"""
+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
+"""
+
+
+class Solution:
+    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
+        m, n = len(matrix), len(matrix[0])
+        for i in range(1, m):
+            for j in range(n):
+                if matrix[i][j] == 1:
+                    matrix[i][j] += matrix[i - 1][j]
+        ans = 0
+        for i in range(m):
+            matrix[i].sort()
+            for j in range(n):
+                height = matrix[i][j]
+                ans = max(ans, height * (n - j))
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.largestSubmatrix(matrix=[[0, 0, 1], [1, 1, 1], [1, 0, 1]]))
+    print(obj.largestSubmatrix(matrix=[[1, 0, 1, 0, 1]]))
+    print(obj.largestSubmatrix(matrix=[[1, 1, 0], [1, 0, 1]]))