✅ Beats 100% - Explained with [ Video ] - Simple Sorting - Visualized Too
\n\n # YouTube Video Explanation:\n\n<a href="https://youtu.be/biPaIwFMISI">https://youtu.be/biPaIwFMISI</a>\n\n**\uD83D\uDD25 Please like, share, and subscribe
![Screenshot 2023-11-26 085349.png](https://assets.leetcode.com/users/images/07ea17af-c17d-4dd3-be57-e1a8b31a82d3_1700969160.5604217.png)\n\n<!-- # YouTube Video Explanation:\n\n[https://youtu.be/biPaIwFMISI](https://youtu.be/biPaIwFMISI)\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 500 Subscribers*\n*Current Subscribers: 429*\n\n--- -->\n# 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\n**Step 1: Preprocessing**\n```\n[\n [0, 0, 1],\n [1, 1, 2],\n [2, 0, 3]\n]\n```\n- For 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- 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\n<!-- Describe your first thoughts on how to solve this problem. -->\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\n<!-- Describe your approach to solving the problem. -->\n1. Iterate through the matrix starting from the second row (`i = 1`).\n2. For each cell `matrix[i][j]`:\n   - 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]`).\n3. After preprocessing, for each row, sort the row in non-decreasing order.\n4. For each cell in the sorted row, calculate the area of the submatrix that ends at this cell, considering the consecutive 1s.\n   - 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.\n   - Update the maximum area accordingly.\n5. 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 []\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```cpp []\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```python []\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```javascript []\nvar largestSubmatrix = function(matrix) {\n    const m = matrix.length;\n    const n = matrix[0].length;\n\n    for (let i = 1; i < m; ++i) {\n        for (let j = 0; j < n; ++j) {\n            if (matrix[i][j] === 1) {\n                matrix[i][j] += matrix[i - 1][j];\n            }\n        }\n    }\n    \n    let ans = 0;\n    \n    matrix.forEach(row => {\n        row.sort((a, b) => b - a);\n        for (let j = 0, k = 1; j < n && row[j] > 0; ++j, ++k) {\n            const s = row[j] * k;\n            ans = Math.max(ans, s);\n        }\n    });\n    \n    return ans;\n};\n```\n<!-- ![upvote1.jpeg](https://assets.leetcode.com/users/images/1ea0c5b1-7921-4339-8b33-2e9decc9c650_1700969083.5138505.jpeg) -->\n
['Array', 'Greedy', 'Sorting', 'Matrix', 'Python', 'C++', 'Java', 'JavaScript']