aboutsummaryrefslogtreecommitdiff
path: root/largest_submatrix.c
blob: 4caa160046fc03ea669d548f9f466fe89da1d8b8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
}