Optimal O(m*n) time, O(n) space, no sort :)
We first explain an O(m * n * log n) algorithm that, internally, uses an O(n * log n) sort for each row.  That algorithm is similar to most other solutions for 
We first explain an O(m * n * log n) algorithm that, internally, uses an O(n * log n) sort for each row.  That algorithm is similar to most other solutions for this problem.  It is good-enough for the current tests, but not optimal.  Then, we explain how to remove that sort() and obtain an O(m * n) algorithm.  Finally, we prove that our algorithm is asymptotically optimal.\n\n### **First try: O(m * n * log n) algorithm**\n\nThe algorithm processes the matrix row by row, starting from the top row.  Each iteration r examines submatrices that "end" at the current row r (i.e., the max row for elements of that submatrix is r) and finds the one with the max area.  Each such submatrix consists of a few contiguous "towers of 1s" truncated to their smallest height.  Each "tower of 1s" corresponds to a column c where matrix[r\'][c] is 1 for all r\' in [r_start, r], for some r_start <= r.\n\nFor example, for the matrix from the picture below, assume we are currently examining row 3:\n\n![image](https://assets.leetcode.com/users/images/21fdae13-2f58-4a64-bbba-c13edaa8b3ad_1610915897.0921552.png)\n\nIn row 3, we have 1 elements in columns 0, 2, 4, and 5.  These 1 elements are part of some contiguous "towers of 1s".  E.g., we have a tower of a single 1 in column 0, a tower of two 1s in column 2, a tower of four 1s in column 4, and a tower of two 1s in column 5.  Notice that the 1s from position (0,0) and (1,0) are irrelevant, due to the 0 from (2,0), which separates them from the 1 at (3,0): when we examine row r (in this case row 3) we are interested in "towers of 1s" that end at row r (not earlier).  We are also not interested in the continuation of these towers "downward" (e.g., the 1 from (4, 4)); those continuations will be examined when we examine later rows.\n\nThe heights of these "towers of 1s" are [1, 2, 4, 2] (towers of height zero are irrelevant).  As we move from row to row, we can compute the heights of these towers in O(n) time per row: if matrix[r][c] is 1, we increment the height of the tower from column c; otherwise, we set it to 0.\n\nAny submatrix that "ends" in row 3 uses some of these "towers of 1s".  As we can swap columns, it\'s irrelevant how far apart these towers are: we can always bring them together.  E.g., we can bring columns 2, 4, and 5 together, and truncate them at height 2 to obtain a submatrix of size 3 * 2 = 6.  In general, given a desired height h of the resulting submatrix, we can select all columns of height >= h.\n\nLet\'s rearrange the columns in decreasing order of the height of their towers of 1s:\n\n![image](https://assets.leetcode.com/users/images/4d23afbd-210b-4697-8020-feb94f347ce1_1610916385.9401817.png)\n\nThe non-empty towers of 1s are [4, 2, 2, 1].  After this sort / rearrangement, if column i appears in the submatrix, then we should include all columns j <= i: due to the decresing order, they are at least as tall as column i; also, as we want the max-area submatrix, we include all columns that we can.  I.e., we have i+1 columns (= the width of the submatrix) and the resulting submatrix has height equal to the height of the tower of 1s from column i.\n\nIn our example, if we select column 0, then we get a submatrix consisting of only this column, of area 1x4 = 4.  If we select column 1, we get a submatrix consisting of the first 1+1=2 columns, and height 2, i.e., an area 2x2=4.  If we select column 2, we get a submatrix consisting of the first 2+1=3 columns, and height 2, i.e., an area 3x2=6.  Finally, if we select column 3, we end up with a submatrix of area 4x1=4.  The maximum area of a matrix that ends at row 3 is 6.\n\nThese are the reasons most solutions (1) examine the input matrix row by row, (2) compute the tower heights, and (3) sort them (with equivalent variations: e.g., some sort them in increasing, some in decreasing order).  This algorithm has complexity O(m * n * log n): for each of the O(m) rows, we scan all n row elements to update the tower heights, then sort the tower heights (in O(n * log n)) and next do another linear scan over the sorted vector to find the max-area submatrix.\n\nIn C++, we have\n\n```\n// Sub-optimal O(m * n * log n) solution:\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        const int m = matrix.size();     // number of rows\n        const int n = matrix[0].size();  // number of columns\n        \n        // tower[r][c] = height of the contiguous "tower\n        // of 1s" that ends in (r, c).  0 if no such tower.\n        vector<vector<int>> tower(m, vector<int>(n, 0));\n        \n        // Compute, in O(m * n), all elements of tower:\n        //        \n        // Init first row, tower[0]:\n        for (int c = 0; c < n; c++) {\n            tower[0][c] = matrix[0][c];\n        }\n        \n        // Compute each subsequent row, in order:\n        for (int r = 1; r < m; r++) {\n            for (int c = 0; c < n; c++) {\n                if (matrix[r][c] == 1) {\n                    // 1 element => continue the tower in column c:\n                    tower[r][c] = tower[r-1][c] + 1;\n                } else {\n                    // 0 element => reset the tower in column c:\n                    tower[r][c] = 0;\n                }\n            }\n        }\n\n        int max_area = 0;\n        \n        // Iterate over all rows:\n        for (int r = 0; r < m; r++) {\n            // Examine submatrices that end on row r:\n            sort(tower[r].begin(), tower[r].end(), greater<int>());\n            for (int c = 0; c < n; c++) {\n                max_area = std::max(max_area, (c+1) * tower[r][c]);\n            }            \n        }\n        return max_area;\n    }\n};\n```\n\nMany small optimizations are possible: e.g., one can store the tower heights in the original `matrix`, which avoids the need to allocate a new matrix.  One can also merge the two traversals (the one that computes `tower` and the one that uses it), etc.  In the next section, we present an optimization that reduces the asymptotic complexity.\n\n### **Better: O(m * n) algorithm**\n\n**Intuition #1**: very similar to the previous algorithm, but we maintain the list of the heights of the towers of 1s in a way that is always sorted in decreasing order.  This means we do not need to do an explicit sort for each row.\n\n**Intuition #2**: The "tower height" information for row r (see previous paragraph) can be computed using the similar information for the previous row:\n* we increment the height of each existing "tower of 1s" that continues in this row: e.g., a tower in column c, such that matrix[r][c] is 1.\n* we drop other "towers of 1s": e.g., a tower in column c, such that matrix[r][c] == 0.\n* we possibly start new "towers of 1s" of height 1 if matrix[r][c] is 1 and there was no tower in that column for the previous row.\n\nAccordingly, given the list of "towers of 1s" that end on the previous row (in decreasing order of their heights), we selectively copy some of them (incrementing their heights), skip some other towers, and add some 1s at the end of the list.  This can be done in O(n).  If the previous list was in decreasing order, the resulting list is also in decreasing order.\n\nThe original list is empty, which is trivially sorted.  Each subsequent step maintains the decreasing order, as explained by the previous paragraph.\n\nThe code below fills in the details.\n\n```\n// O(m * n) solution:\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        const int m = matrix.size();\n        const int n = matrix[0].size();\n        int max_area = 0;\n\n        // The loop below explores `matrix`, row by row, from the top.\n        // After processing row r, `towers` contains pairs <h, c>,\n\t\t// where h is the height of the "contiguous tower of 1s" that\n\t\t// ends at matrix[r][c], for each c such that matrix[r][c] == 1.\n        //\n        // `towers` has O(n) elements: at most one pair for each column.\n        //\n        // The pairs from `towers` are sorted in decreasing order of\n        // their first component (the tower height).\n        vector<pair<int, int>> towers;\n        for (int r = 0; r < m; r++) {\n            // Updated version of towers, for the current row r.\n            vector<pair<int, int>> next;\n            \n            // done[c] is true iff the "tower of 1s" that ends\n            // in matrix[r][c] has already been considered and\n            // a pair for it already exists in next.\n            vector<bool> done(n, false);\n            \n            // Two ways to build "towers of 1s":\n            // (1) Extend existing towers (if possible).\n            for (const auto &p : towers) {\n                const int c = p.second;\n                if (matrix[r][c] == 1) {\n                    next.emplace_back(p.first + 1, c);\n                    done[c] = true;\n                } else {\n                    // As matrix[r][c] == 0, there is no tower of 1s\n                    // ending at (r, c) => we drop this tower (= not\n                    // copy it into `next`).\n                }\n            }\n            \n            // (2) Start new towers (of height 1) for 1 elements\n            // that did not have a tower above them:\n            for (int c = 0; c < n; c++) {\n                if (!done[c] && matrix[r][c] == 1) {\n                    next.emplace_back(1, c);\n                }\n            }\n\n            towers = std::move(next);\n\t\t\t\n\t\t\t// Examine heights of the towers of 1s, in decreasing order.\n            for (int i = 0; i < towers.size(); i++) {\n\t\t\t    // Any max-area submatrix that includes tower i, also\n\t\t\t\t// includes all towers j <= i (i+1 towers in total).\n                max_area = max(max_area, (i + 1) * towers[i].first);\n            }\n        }\n\n        return max_area;\n    }\n};\n```\n\n### **Optimality Proof**\n\nOur O(m * n) time-complexity algorithm is asymptotically optimal. \n\nProof: each correct algorithm must examine each element of the input matrix: e.g., consider an input matrix that is 1 everywhere, except in the one element that we don\'t read.  Then, we have no way of knowing whether the correct answer is m * n or something strictly smaller that does not include that element.  Hence, the asymptotic complexity of any correct algorithm is at least O(m * n), which means that our algorithm is asymptotically time optimal; "asymptotically" means that one can "fiddle" with the implementation, making it faster or slower, but the complexity is still big-O (m * n).\n
[]