Java | Basic Math + Intuitive
Approach:\nJust use basic math for AreaOfRectangle = height * width\nNow all we need is height and width for each cell while calculating area (that cell being t
**Approach**:\nJust use basic math for **AreaOfRectangle = height * width**\nNow all we need is **height and width for each cell while calculating area** (that cell being the bottom right end of the rectangle being considered)\n\nThis can be done in following 2 major steps:\n1. Modify matrix values to keep track of max height for each cell (height increases with continuous sequence of ```1```\'s)\n1.1. Sort row values in non-decreasing order (as columns can be moved)\n\t\t[Here, sorting retains the column values of respective columns i.e. whole columns are moved. (Try dry-run to understand \'how?/why?\')]\n2. Calculate width on the fly while calculating area till each cell (traversing row wise).\n```\nclass Solution {\n    public int largestSubmatrix(int[][] matrix) {\n        // modify matrix values in-place to keep track of max heights\n\t\tfor(int i = 1; i < matrix.length; ++i)\n\t\t\tfor(int j = 0; j < matrix[i].length; ++j)\n\t\t\t\tif(matrix[i][j] != 0) matrix[i][j] += matrix[i - 1][j];\n        \n\t\tint maxArea = 0;\n\t\tfor(int i = 0; i < matrix.length; ++i) {\n\t\t\t// sort rows in non-decreasing order \n\t\t\tArrays.sort(matrix[i]);\n\t\t\tfor(int j = 0; j < matrix[i].length; ++j)\n\t\t\t\t// height = matrix[i][j]; width = matrix[i] - j\n\t\t\t\t// areaOfRectangle = height * width\n\t\t\t\tmaxArea = Math.max(maxArea, matrix[i][j] * (matrix[i].length - j));\n\t\t}\n\t\treturn maxArea;\n    }\n}\n```
['Math']