😀 Fully Explained Solution With Example and Dry Run 💡
Problem \nFinding the maximum area of submatrix which has 1 in its each cell.\n\n# How do we calculate area?\nArea = Length * breadth\nIn this problem, we will 
# Problem \nFinding the maximum area of submatrix which has 1 in its each cell.\n\n# How do we calculate area?\n**$$Area = Length * breadth$$**\nIn this problem, we will calculate through **width** and **height**.\n\n**But wait, how to find the height \uD83E\uDD14?**\nWell, we have to find the height of those cells that have 1.\n\nIt can be understood through an example.\nFor example \n```\n         0   0   1\nmatrix = 1   1   1\n         1   0   1\n```\nIn first column, start from top to down -\n\n1. height of 0 = 0\n2. height of 1 = 1\n3. height of 1 = 2 (why 2? since there is already one element with value 1 above the 1 of third row).\n\nso the matrix becomes - \n```\n         0   0   1\nmatrix = 1   1   1\n         2   0   1\n```\nIn second column, start from top to down -\n\n1. height of 0 = 0\n2. height of 1 = 1\n3. height of 0 = 0 (since we don\'t want the submatrix with 0, so we will not calculate its height or its height will beome 0).\n\nso the matrix becomes - \n```\n         0   0   1\nmatrix = 1   1   1\n         2   0   1\n```\nIn third column, start from top to down -\n\n1. height of 1 = 1\n2. height of 1 = 2\n3. height of 1 = 3 (since we don\'t want the submatrix with 0, so we will not calculate its height or its height will beome 0).\n\nso the matrix becomes - \n```\n         0   0   1\nmatrix = 1   1   2\n         2   0   3\n```\n\nIf we **sort** the matrix in **ascending order** then all the cells with highest height will shift towards right.\n\nso the final becomes - \n```\n         0   0   1\nmatrix = 1   1   2\n         0   2   3\n```\n\nNow observe , that the cell with maximum height will be from bottom down corner. while move from the last cell towards first, we observe that the height is getting decreased.\n\n**Maximum height and maximum width = maximum area**\n\nIf we start iterating the last element (3), width is 1 and height is 3, so the area  becomes = 3.\n\nBut wait, can we get more area than this? May be!\n\nSo we move to last second element (2) and take the width as 2.\nBut why the height is 2.\n\nSince every cell right to the current element (2) has the height greater than the current (2). So the right columns  automatically involve in the area while calculating.\n\nSo the area becomes 2*2 = 4.\n\nSince it is getting complexed, so lets\'s name the cells as 1st, 2nd, 3rd, 4th, ... 9th. Remember that the naming is done by left to right.\n\n```\n         0   0   1\nmatrix = 1   1   2\n         0   2   3\n```\n\n1st cell = 0\n2nd cell = 0\n3rd cell = 1\n4th cell = 1\n5th cell = 1\n6th cell = 2\n7th cell = 0\n8th cell = 2\n9th cell = 3\n\nStart from the last cell\n**1st Iteration :-**\n**$$cell = 9th$$**\n**$$width = 1$$**\n**$$height = 3$$**\n**$$area = width*height = 1 * 3 = 3$$**\n\n**2nd Iteration :-**\n**$$cell = 8th$$**\n**$$width = 2$$**\n**$$height = 2$$**\n**$$area = width*height = 2 * 2 = 4$$**\n\n\n**4th Iteration :-**\n**$$cell = 6th$$**\nSince we are again at the last column, so the width is resetted to 1.\n**$$width = 1$$**\n**$$height = 2$$**\n**$$area = width*height = 1 * 2 = 2$$**\n\n**5th Iteration :-**\n**$$cell = 5th$$**\n**$$width = 2$$**\n**$$height = 1$$**\n**$$area = width*height = 2 * 1 = 2$$**\n\n**6th Iteration :-**\n**$$cell = 4th$$**\n**$$width = 3$$**\n**$$height = 1$$**\n**$$area = width*height = 3 * 1 = 3$$**\n\n**7th Iteration :-**\n**$$cell = 3th$$**\nSince we are again at the last column, so the width is resetted to 1.\n**$$width = 1$$**\n**$$height = 1$$**\n**$$area = width*height = 1 * 1 = 1$$**\n\n**8th Iteration :-**\n**$$cell = 2th$$**\n**$$width = 2$$**\n**$$height = 0$$**\n**$$area = width*height = 2*0 = 0$$**\n\n**9th Iteration :-**\n**$$cell = 1th$$**\n**$$width = 3$$**\n**$$height = 0$$**\n**$$area = width*height = 3*0 = 0$$**\n\nMaximum area is obtained is 4th in second iteration. So this is the answer.\n\n# Complexity\n- Time complexity: $$O(m*nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix) {\n        int m = matrix.size();\n        int n = matrix[0].size();\n        int area = 0;\n\n        for(int i=1; i<m; i++){\n            for(int j=0; j<n; j++){\n                if(matrix[i][j]==1){\n                    matrix[i][j] += matrix[i-1][j];\n                }\n            }\n        }\n\n        for(int i=m-1; i>=0; i--){\n            sort(matrix[i].begin(), matrix[i].end());\n            int k = 1;\n            for(int j=n-1; j>=0; j--){\n                area = max(area, matrix[i][j]*k);\n                k++;\n            }\n        }\n\n        return area;\n        \n\n        return area;\n    }\n};\n```
['C++']