Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 26

Description

Largest Submatrix With Rearrangements

You are given a binary matrix matrix of size m x 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 the columns optimally.

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m * n <= 105
• matrix[i][j] is either 0 or 1.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int largestSubmatrix(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix.front().size();

    int answer = 0;
    for(int row = 0; row < rows; ++row) {
      for(int col = 0; col < cols; ++col) {
        if(matrix[row][col] && row) {
          matrix[row][col] += matrix[row - 1][col];
        }
      }

      vector<int> currentRow = matrix[row];
      sort(currentRow.rbegin(), currentRow.rend());
      for(int i = 0; i < cols; ++i) {
        answer = max(answer, currentRow[i] * (i + 1));
      }
    }

    return answer;
  }
};

// Accepted
// 58/58 cases passed (168 ms)
// Your runtime beats 36.93 % of cpp submissions
// Your memory usage beats 60.8 % of cpp submissions (74.7 MB)