Easy Python Solution - Beats 100%
Intuition\nThe problem requires finding the largest submatrix within the given matrix, where every element of the submatrix is 1, after reordering the columns o
# Intuition\nThe problem requires finding the largest submatrix within the given matrix, where every element of the submatrix is 1, after reordering the columns optimally.\n# Approach\n- Initialize variables m and n to store the number of rows and columns in the matrix, respectively.\n- Iterate over the matrix from the second row onwards (index i from 1 to m-1):\n    - For each row, iterate over all columns (index j from 0 to n-1):\n        - If the current cell value is 1, add the value of the corresponding cell in the previous row to the current cell. This step accumulates the number of consecutive 1s vertically.\n- Initialize a variable ans to store the maximum area of the submatrix initialized to 0.\n- Iterate over each row in the matrix:\n    - Sort the row in reverse order. This step rearranges the elements in descending order based on the accumulated consecutive 1s. By doing this, the largest submatrix will consist of consecutive 1s from left to right.\n    - Iterate over each column (index j from 0 to n-1):\n        - Update ans by calculating the maximum of the current value of ans and the product of the current element in the sorted row and the column index j + 1. This step calculates the area of the submatrix composed of consecutive 1s.\n- Return the value of ans, which represents the area of the largest submatrix with all 1s after reordering the columns optimally.\n# Complexity\n- Time complexity: The code consists of two nested loops iterating over the rows and columns of the matrix. Hence, the time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix.\n- Space complexity: The code utilizes a constant amount of extra space to store the variables. Therefore, the space complexity is O(1).\n\n![image.png](https://assets.leetcode.com/users/images/29f0a913-a131-460f-ad6a-e95efa224512_1701016113.3160844.png)\n\n\n# Code\n```\nclass Solution(object):\n    def largestSubmatrix(self, matrix):\n        m, n = len(matrix), len(matrix[0])\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        ans = 0\n        for r in matrix:\n            r.sort(reverse=True)\n            for j in range(n):\n                ans = max(ans, r[j] * (j + 1))\n        \n        return ans        \n```
['Python']