Explanation with Picture. Variation of Maximal Rectangle and Largest Rectangle in Histogram
This problem is very similar to Maximum rectangular area and Largest Rectangle in Histogram. The only variation here is that we can swap the columns and put the
This problem is very similar to Maximum rectangular area and Largest Rectangle in Histogram. The only variation here is that we can swap the columns and put the columns next to each other to optimize the answer.\n\nWell, we can just sort the current row in which we are and then can directly use `largestRectangularArea` function.\n\nHow i figured this out?\nI submitted WA first then I got that hint.\nConsider the current row to be [1,2,1,1,0,2,2]\nIf you solve it without sorting then you will calculate the wrong answer.\n\nWe need to do this for every row because it is possible  that all the values in next row is zero then we will lose the sum we got so far from columns above the particular row.\n\nEvery cell will have cell_val (if cell value == 1) = 1 + sum of cell above it.\n\t\t\t\t\t\t\t\totherwise cell_val = 0 because we can\'t have empty cells in our submatrix.\n\n![image](https://assets.leetcode.com/users/images/1cbad855-2bb3-442d-b454-7613936d7e55_1610855378.8840451.png)\n\nEdit: Max ans in 4th row should be 3 not 1 as noticed by @mcclay. After sorting all 1s would come together.\n\nNotice that in the last row we used sorting so that columns ending up with value 2 are next to each other. If we don\'t do this then we are not taking the benefit of question statement to swap columns and put them next to each other.\n\nEdit: As suggested by @ArshadAQ there is no need to use stack to find largestRectangularArea as in maximal rectangle problem as we are allowed to reorder. \nSo, updating largestRectangleArea function.\n\nFinally, here is the code.\n```\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        \n        int rows = matrix.size();\n        int cols = matrix[0].size();\n        \n        for(int i = 1; i < rows; i++)\n        {\n            for(int j = 0; j < cols; j++)\n            {\n                if(matrix[i-1][j] && matrix[i][j]) matrix[i][j] = matrix[i-1][j]+1;\n            }\n        }\n                \n        int maxval = INT_MIN;\n        for(vector<int> v : matrix)\n            maxval = max(maxval, largestRectangleArea(v));\n    \n        return maxval;\n    }\n    \n    int largestRectangleArea(vector<int>& heights) {\n        sort(heights.begin(), heights.end(), greater<int>());\n        \n        int res = INT_MIN;\n        int minval = INT_MAX;\n        \n        for(int i = 0; i < heights.size(); i++)\n        {\n            minval = min(minval, heights[i]);\n            res = max(res, minval*(i+1));   \n        }\n        \n        return res;\n};\n```\n
[]