https://leetcode.com/problems/largest-submatrix-with-rearrangements/ from Google

Thinking process:

From the constraint, we know that we need to use either O(NlogN) or O(N) algorithm. Since we can rearragnge the columns, it’s very easy to think that one possible answer is the max of sum of each row (the single row case).

What if the answer consists of multiple rows? Let’s say if the red rectangle below is the solution, and blue area means that there are consecutive 1s. If we look at the row r1, we basically want to know how many columns having the blue area starting from r1 which is greater than the smallest blue area. So we can sort by the size of the blue area, or we can use a multiset in C++.

The below code is doing two things. Sum each row and take the max as the answer. And then calculate the blue area at each position. I count the consecutive 1 row by row like below, and use a multiset to sort them, and then compute the area.

Here is the code.

 1class Solution {
 2public:
 3    int largestSubmatrix(vector<vector<int>>& matrix) {
 4        unordered_map<int, multiset<int>> mp;
 5        int ans = 0;
 6        for (auto r : matrix) {
 7            ans = max(ans, accumulate(r.begin(), r.end(), 0));
 8        }
 9        int C = matrix[0].size();
10        int R = matrix.size();
11        for (int i=0; i<C; i++) {
12            int cnt = 0;
13            for (int j=0; j<R; j++) {
14                if (matrix[j][i] == 0) {
15                    cnt = 0;
16                } else {
17                    cnt++;
18                    mp[j].insert(cnt);
19                }
20            }
21        }
22        for (auto [k, v] : mp) {
23            int l = v.size();
24            for (auto x : v) {
25                ans = max(ans, x*l);
26                l--;
27            }
28        }
29        return ans;
30    }
31};