Maximum all 1s submatrix

1727. Largest Submatrix With Rearrangements

The problem is a weekly contest of Jan 16, 2021 for LeetCode. It is a very common problem. For this kind of problem, we usually can optimize the computation by using prefix sum technology.

Prefix sum + two layer loops.

• Calculate prefix sum for each column
• for all possible combinations of row ranges, check the maximum possible submatrix after rearrangement.

It has the complexity of O(C*R²) as R can be as large as 10⁵, it is supposed to get TLE.

When C = 1, R will be 10⁵, add a special case for this one plus early pruning, we can get AC.

The code is shown here.

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& a) {
        const int R = a.size();
        const int C = a[0].size();
       // cout<<R<<" "<<C<<endl;
        int ret = 0;
        int this_ret = 0;
        // quick check when num of column is 1 to get rid of TLE
        if (C == 1) {
            for (int i =0; i < R;++i){
                if (a[i][0]){
                    this_ret++;
                } else {
                    ret = max(ret, this_ret);
                    this_ret = 0;
                }
            }
             ret = max(ret, this_ret);
            return ret;
        }
       
        
        for (int j = 0; j < C; ++j) {
            for (int i = 1; i < R; ++i){
                a[i][j] += a[i-1][j];
            }
        }
      
        int count = 0;
        for (int i = 0; i < R; ++i) {
            for (int j = i; j < R; ++j) {
                count = 0;
                int n = j- i +1;
                // early pruning to get rid of TLE
                if (n*C <= ret) continue;
                for (int k = 0; k < C; ++k) {
                    if (i==0 && a[j][k]==n) count++;
                    if (i!=0 && a[j][k] - a[i-1][k]==n)count++;
                }
                ret = max(ret, count*n);
            }
        }
        return ret;
    }
};

A better code from int65536

The code from int65536 is pretty elegant. The code is shown below.

class Solution
{
public:
    int largestSubmatrix(vector<vector<int>>& a) 
 {
  int n = a.size();
  int m = a[0].size();
  vector<int> count(m);
  int result = 0;
  for (int i = 0; i < n; ++i) {
   for (int j = 0; j < m; ++j) {
    count[j] = (a[i][j] ? count[j] + 1 : 0);
   }
   vector<int> b = count;
   sort(b.begin(), b.end());
   reverse(b.begin(), b.end());
   for (int j = 0; j < m; ++j) {
    result = max(result, (j + 1) * b[j]);
   }
  }
  return result;
 }
};

I am trying to understand the above code and here is my understanding:

//1) get the number of continuous 1s up to the row i
count[j] = (a[i][j] ? count[j] + 1 : 0);
//2) sort the count reversely -> from largest to smallest 
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
//3) loop the column and harvest the results. As j is from 0, we should add j by 1.
(j + 1) * b[j]

The above solution is pretty smart. The complexity will be:

step 1): O(C)

step 2) O(C log C)

step 3) O(C)

As we have another layer loop to traverse all rows, the overall complexity is:

O(R*((C + C log C + C)) = O(R*C* log C)

As the maximum value of (R*C) is 10⁵, so the overall complexity is O(10^5 * log C). It is pretty fast.