[JS] DP (w/Explanation) | Beats 90.91% & 72.73%
Intuition\nUpon encountering this problem, the first idea is to maximize the area of 1s in a binary matrix by rearranging the columns. A key realization is that
# Intuition\nUpon encountering this problem, the first idea is to maximize the area of 1s in a binary matrix by rearranging the columns. A key realization is that we can count the number of 1s in each column and then sort these counts row by row. This sorting effectively simulates rearranging the columns so that rows with more 1s are aligned together, thereby potentially forming larger rectangles of 1s. The challenge lies in figuring out the best way to calculate the maximum area of the submatrix after this rearrangement.\n\n# Approach\n1.) **Column-wise 1s Counting:** Iterate through the matrix. For each cell that is a 1, add to its value the value of the cell directly above it. This process transforms each cell to represent the height of a \'tower\' of 1s in that column up to the current row, effectively creating a histogram in each row.\n\n**2.) Row-wise Sorting:** Sort the counts in each row in non-increasing order. This step is crucial as it simulates the rearrangement of columns such that those with more 1s are moved to the left, thereby maximizing the potential area of rectangles formed by consecutive 1s.\n\n**3.) Area Calculation:** Iterate over each row. For each cell, calculate the area of the rectangle that could be formed with the cell\'s value as the height. This is done by multiplying the value (height of the rectangle) by the column index plus one (as the width). Keep track of and update the maximum area found.\n\n# Complexity\n- Time complexity: O($$m$$\xD7$$n$$log$$n$$) (Runtime: 119ms, beats 90.91%)\n    - Step 1, counting 1s in each column, requires O($$m$$\xD7$$n$$) as it involves a single pass through all elements. \n    - Step 2, the sorting step, has a complexity of O($$n$$log$$n$$) for each row, and since there are $$m$$ rows, the total complexity for sorting is O($$m$$\xD7$$n$$log$$\u2061n$$).\n    - Step 3, the final area calculation, requires a pass through all elements, adding another O($$m$$\xD7$$n$$), which does not dominate the sorting complexity.\n\n- Space complexity: O(1) (Runtime: 70.2mb, beats 72.73%)\n    - The space complexity is O(1) if we disregard the input space, as the transformation is done in-place and no additional significant space is used. If we consider the input space, then the space complexity is O($$m$$\xD7$$n$$), which is the size of the input matrix.\n    - Runtime: \n\n# Code\n```\n/**\n * @param {number[][]} matrix\n * @return {number}\n */\n\nfunction largestSubmatrix(matrix) {\n    const m = matrix.length, n = matrix[0].length;\n    let maxArea = 0;\n\n    // Step 1: Count 1s in each column\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    // Step 2: Sort counts in each row\n    for (let i = 0; i < m; i++) {\n        matrix[i].sort((a, b) => b - a);\n    }\n\n    // Step 3: Calculate maximum area\n    for (let i = 0; i < m; i++) {\n        for (let j = 0; j < n; j++) {\n            maxArea = Math.max(maxArea, matrix[i][j] * (j + 1));\n        }\n    }\n\n    return maxArea;\n}\n\n```
['Dynamic Programming', 'Greedy', 'Sorting', 'Matrix', 'JavaScript']