C++ sort row vs Freq count||124 ms Beats 98.30%
Intuition\n Describe your first thoughts on how to solve this problem. \nUse the matrix to store the height for each column.\n\nLater try other approach!\n# App
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse the `matrix` to store the height for each column.\n\nLater try other approach!\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse sort!\n\nThe approach using counting sort leads to TLE & fails , for the testcase `100000*[[1]]`. After some trials( one using hash table(unordered_map), other using array), it is finally accepted!\n\nThe revised code using  counting sort with special dealing n=1 & m=1 cases (thanks to the idea of @Sergei ) becomes a fast code which runs in 124 ms & beats 98.30%!\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nm \\log n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ \n# Code 136 ms Beats 93.75%\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int m=matrix.size(), n=matrix[0].size();\n        int area=count(matrix[0].begin(), matrix[0].end(), 1);\n        for(int i=1;  i<m; i++){\n            #pragma unroll\n            for(int j=0; j<n; j++){\n                if (matrix[i][j]!=0)\n                    matrix[i][j]+=matrix[i-1][j];\n            }\n            auto row=matrix[i];\n            sort(row.begin(), row.end());\n            #pragma unroll\n            for(int i=0; i<n; i++)\n                area=max(area, row[i]*(n-1-i+1));\n        }\n        return area;\n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# revised Code using Frequency Count 124 ms Beats 98.30%\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:  \n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int m=matrix.size(), n=matrix[0].size();\n        int area=count(matrix[0].begin(), matrix[0].end(), 1);\n        if (m==1) return area;\n        if (n==1){\n            #pragma unroll\n            for(int i=1; i<m; i++){\n                if (matrix[i][0]!=0)\n                    matrix[i][0]+=matrix[i-1][0];\n                area=max(area, matrix[i][0]);\n            }\n            return area;\n        }\n        \n        #pragma unroll\n        for(int i=1; i<m; i++){\n            #pragma unroll\n            for(int j=0;  j<n; j++){\n                if (matrix[i][j]!=0)\n                    matrix[i][j]+=matrix[i-1][j];\n            }\n       \n            auto row=matrix[i];\n            int minH=i+1, maxH=0;\n            #pragma unroll\n            for(int x: row){\n                minH=min(minH, x);\n                maxH=max(maxH, x);\n            }\n            vector<int> freq(maxH-minH+1, 0);\n            #pragma unroll\n            for(int x: row){\n                freq[x-minH]++;\n            }\n            int acc=0;\n            #pragma unroll\n            for(int x=maxH-minH; acc<n; x--){\n                if (freq[x]>0){\n                    acc+=freq[x];\n                    area=max(area, acc*(x+minH));\n                }\n            }  \n        }\n        return area;\n    }\n};\n\n```\n# Code using Frequency Count & Hash table\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:  \n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int m=matrix.size(), n=matrix[0].size();\n        int area=count(matrix[0].begin(), matrix[0].end(), 1);\n        #pragma unroll\n        for(int j=0; j<n; j++){\n            #pragma unroll\n            for(int i=1;  i<m; i++){\n                if (matrix[i][j]!=0)\n                    matrix[i][j]+=matrix[i-1][j];\n            }\n        }\n        unordered_map<int, int> freq;\n        #pragma unroll\n        for(int i=0;  i<m; i++){\n            auto row=matrix[i];\n            freq.clear();\n            int maxH=0;\n            #pragma unroll\n            for(int x: row){\n                maxH=max(maxH, x);\n                freq[x]++;\n            }\n            int acc=0;\n            #pragma unroll\n            for(int x=maxH; acc<n; x--){\n                if (freq.count(x)>0){\n                    acc+=freq[x];\n                    area=max(area, acc*x);\n                }\n            }  \n        }\n        return area;\n    }\n};\n```\n
['Array', 'Hash Table', 'Sorting', 'Counting Sort', 'C++']