Java Solution for Largest Submatrix With Rearrangements Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe approach aims to find the largest submatrix containing only 1s after rearranging th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe approach aims to find the largest submatrix containing only 1s after rearranging the columns optimally. It works by first computing the height of each column by counting the consecutive 1s from the top. Then, it sorts each row\u2019s heights to determine the maximum area by considering the maximum consecutive 1s in a row, multiplied by its width.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tCompute the height of consecutive 1s in each column by iterating through the matrix.\n2.\tStore these heights in a separate 2D array.\n3.\tSort each row\u2019s heights array to find the maximum consecutive 1s for each column.\n4.\tCalculate the maximum area by multiplying the maximum height in a row by its width (the number of columns).\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tComputing the heights for each cell in the matrix takes O(m * n) time.\n\u2022\tSorting each row\u2019s heights takes O(m * n * log n) time.\n\u2022\tFinding the maximum area involves traversing the sorted heights, which takes O(m * n) time.\nOverall, the time complexity is O(m * n * log n) due to the sorting step dominating the computation.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tThe space complexity is O(m * n) because we create a 2D heights array to store the heights of consecutive 1s for each cell in the matrix.\n\u2022\tAdditionally, there\u2019s some extra space used for variables and temporary storage, but they don\u2019t significantly impact the overall space complexity.\n\n# Code\n```\nclass Solution {\n    public int largestSubmatrix(int[][] matrix) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n\n        // Calculate heights for each column\n        int[][] heights = new int[m][n];\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (matrix[i][j] == 1) {\n                    heights[i][j] = i == 0 ? 1 : heights[i - 1][j] + 1;\n                }\n            }\n        }\n\n        // Sort rows to find the maximum area\n        int maxArea = 0;\n        for (int i = 0; i < m; i++) {\n            Arrays.sort(heights[i]);\n            for (int j = 0; j < n; j++) {\n                maxArea = Math.max(maxArea, heights[i][j] * (n - j));\n            }\n        }\n\n        return maxArea;\n    }\n}\n```
['Java']