90ms C++ beats 100% O(mn)
Before the O(mn) solution, first the O(m n log n) solution (but slightly improved), best time 102ms.\n\n//https://hyper-meta.blogspot.com/\n#pragma GCC target("
Before the O(mn) solution, first the O(m n log n) solution (but slightly improved), best time 102ms.\n```\n//https://hyper-meta.blogspot.com/\n#pragma GCC target("avx,mmx,sse2,sse3,sse4")\nauto _=[]()noexcept{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return 0;}();\nint t[100001];\nint ind[100001];\nint isz;\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        auto &v=matrix[0];\n        int r=accumulate(v.begin(),v.end(),0),s,vj;\n        const int sz=matrix.size(),n=v.size();\n        for(int i=1;i<sz;++i){\n            isz=s=0;\n            auto &v1=matrix[i];\n            for(int j=0;j<n;++j){\n                vj=v[j]=(v[j]+1)*v1[j];\n                if(!vj) continue;\n                if(!t[vj]++) ind[isz++]=vj;\n            }\n            sort(ind,ind+isz);\n            for(int k=isz-1;k>=0;--k){\n                int idx=ind[k];\n                r=max(r,idx*(s+=t[idx]));\n                t[idx]=0;\n            }\n        }\n        return r;\n    }\n};\n```\nHere the columns with the same "row-side length" are combined, so we only sort the number of different sizes, which could be much smaller than $n$.\n\nHere\' s the O(mn) version, the same idea as [explained here](https://leetcode.com/problems/largest-submatrix-with-rearrangements/solutions/1020797/optimal-o-m-n-time-o-n-space-no-sort/), just optimized for speed (also saves some space). Best time 90ms.\n```\n//https://hyper-meta.blogspot.com/\n#pragma GCC target("avx,mmx,sse2,sse3,sse4")\nauto _=[]()noexcept{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return 0;}();\nstruct pa{int cnt,ind;};\npa cnts[100000];\nint csz,nsz;\nbool done[100000];\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        const int m=matrix.size(),n=matrix[0].size();\n        int r=0;\n        csz=0;\n        for(int i=0;i<m;i++) {\n            memset(done,0,n);\n            nsz=0;\n            auto &v=matrix[i];\n            for(int j=0;j<csz;++j){\n                int c=cnts[j].cnt,d=cnts[j].ind;\n                if(v[d]){\n                    cnts[nsz++]=pa{c+1,d};\n                    done[d]=1;\n                }\n            }\n            for(int j=0;j<n;j++) if (!done[j]&&v[j]) cnts[nsz++]=pa{1,j};\n            for(int j=0;j<(csz=nsz);j++) r=max(r,(j+1)*cnts[j].cnt);\n        }\n        return r;\n    }\n};\n```
['C++']