🚀✅🚀 Beats 101% -1727. Largest Submatrix With Rearrangements
Example Explanation\nLet\'s break down the process step by step using an example matrix:\n\nExample Matrix:\n\n[\n [0, 0, 1],\n [1, 1, 1],\n [1, 0, 1]\n]\n\nSte
**Example Explanation**\nLet\'s break down the process step by step using an example matrix:\n\n**Example Matrix:**\n```\n[\n [0, 0, 1],\n [1, 1, 1],\n [1, 0, 1]\n]\n```\n**Step 1: Preprocessing**\n```\n[\n [0, 0, 1],\n [1, 1, 2],\n [2, 0, 3]\n]\n```\nFor each cell matrix[i][j] = 1, update it with the height of consecutive 1s ending at this cell (matrix[i][j] += matrix[i-1][j]).\n\n**Step 2: Sorting Rows**\nSort each row in non-decreasing order.\n```\n[\n [0, 0, 1],\n [1, 1, 2],\n [0, 2, 3]\n]\n```\n\n**Step 3: Calculate Area**\nIterate through each row and calculate the area for each cell.\n```\n[\n [0, 0, 1],   Area: row[j]*k = 1*1\n [1, 1, 2],   Area: Max(row[j]*k) = Max(2x1,1x2,1x3)\n [0, 2, 3]    Area: Max(row[j]*k) = Max(3x1,2x2)\n]\n```\n\n* For each cell, the area is the height * width.\n* For example in the last row, we are moving from backwards to forward, so j starts with n-1 and k=1.\n* In the first iteration row[j]= 3 but k = 1, so area becomes 3 but in the next iteration, row[j]=2 and k=2 so the area becomes 4, which is the maximum of all the areas of submatrix.\n\n**Step 4: Maximum Area**\nThe maximum area among all cells is 4.\n\n**Explanation:**\nThe maximum area of the submatrix containing only 1s after rearranging the columns optimally is 4, achieved at matrix[2][2].\n\n#### Intuition\nThe problem asks for the area of the largest submatrix containing only 1s after rearranging the columns optimally. The solution involves preprocessing the matrix to store the height of consecutive 1s ending at each cell. Then, for each row, we sort the heights in non-decreasing order and calculate the area for each possible submatrix.\n\nThe problem asks for the area of the largest submatrix containing only 1s after rearranging the columns optimally. The solution involves preprocessing the matrix to store the height of consecutive 1s ending at each cell. Then, for each row, we sort the heights in non-decreasing order and calculate the area for each possible submatrix.\n\n### Approach\n1. Iterate through the matrix starting from the second row (i = 1).\n2. For each cell matrix[i][j]:\n3. If matrix[i][j] is 1, update it to store the height of consecutive 1s ending at this cell by adding the height of the previous row\'s corresponding cell (matrix[i - 1][j]).\n4. After preprocessing, for each row, sort the row in non-decreasing order.\n5. For each cell in the sorted row, calculate the area of the submatrix that ends at this cell, considering the consecutive 1s.\n6. The area is given by height * width, where height is the height of consecutive 1s ending at this cell, and width is the position of the cell in the sorted row.\n7. Update the maximum area accordingly.\n8. Return the maximum area as the result.\n\n### Complexity\n* Time Complexity: O(m * n * log(n)) - Sorting is done for each row.\n* Space Complexity: O(1) - No additional space is used except for variables.\n\n# CODE\n\n### Java\n```\nclass Solution {\n    public int largestSubmatrix(int[][] matrix) {\n        int m = matrix.length, n = matrix[0].length;\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] + 1;\n                }\n            }\n        }\n        int ans = 0;\n        for (var row : matrix) {\n            Arrays.sort(row);\n            for (int j = n - 1, k = 1; j >= 0 && row[j] > 0; --j, ++k) {\n                int s = row[j] * k;\n                ans = Math.max(ans, s);\n            }\n        }\n        return ans;\n    }\n}\n```\n\n### C++\n\n```\nclass Solution\n{\npublic:\n    int largestSubmatrix(vector<vector<int>>& matrix)\n    {\n        int m = matrix.size(), n = matrix[0].size();\n        int ans = 0;\n        for(int j = 0; j < n; j++)\n            for(int i = 1; i < m; i++)\n                if(matrix[i][j] == 1)\n                    matrix[i][j] += matrix[i-1][j];\n        for(int i = 0; i < m; i++)\n        {\n            sort(matrix[i].begin(), matrix[i].end());\n            reverse(matrix[i].begin(), matrix[i].end());\n            for(int j = 0; j < n; j++)\n                ans = max(ans, matrix[i][j]*(j+1));\n        }\n        return ans;\n    }\n};\n```\n\nPython\n```\nclass Solution(object):\n    def largestSubmatrix(self, matrix):\n        m, n = len(matrix), len(matrix[0])\n        \n        for i in range(1, m):\n            for j in range(n):\n                if matrix[i][j] == 1:\n                    matrix[i][j] += matrix[i - 1][j]\n        \n        ans = 0\n        \n        for row in matrix:\n            row.sort(reverse=True)\n            for j in range(n):\n                ans = max(ans, row[j] * (j + 1))\n        \n        return ans\n```\n![image](https://assets.leetcode.com/users/images/f7634fc6-f30f-4df2-acff-08c3feaca390_1700994016.0912874.jpeg)\n\n\n
['Array', 'Greedy', 'C', 'Sorting', 'Matrix', 'Python', 'Java', 'JavaScript']