<p>You are given a binary matrix <code>matrix</code> of size <code>m x n</code>, and you are allowed to rearrange the <strong>columns</strong> of the <code>matrix</code> in any order.</p>

<p>Return <em>the area of the largest submatrix within </em><code>matrix</code><em> where <strong>every</strong> element of the submatrix is </em><code>1</code><em> after reordering the columns optimally.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/29/screenshot-2020-12-30-at-40536-pm.png" style="width: 500px; height: 240px;" />
<pre>
<strong>Input:</strong> matrix = [[0,0,1],[1,1,1],[1,0,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/29/screenshot-2020-12-30-at-40852-pm.png" style="width: 500px; height: 62px;" />
<pre>
<strong>Input:</strong> matrix = [[1,0,1,0,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[1,1,0],[1,0,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>matrix[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        """
        neetcode solution.
        https://www.youtube.com/watch?v=NYyIVuSCfOA
        
        Without Modifying Input.

        For every r, c, let us assume there exists
        a rectangle with matrix[r][c] is the 
        bottom-right. Why bottom-right?
        By the time we reached the bottom-right,
        we know that we have looked at all the 
        upper-left cells. By the time we reached
        matrix[nrows-1][ncols-1], then we have
        seen all the other cells already. We know
        if they are 1 or 0. Let's asssume we 
        chose top-left, then we do not really
        know until we check bottom and right 
        cells where 0s/1s are at. 

        Because we can freely rearrange columns, 
        we have good control of the base, but no 
        control on the height. As such, a good 
        first step would be to determine how 
        much height each column contributes on 
        its own.

        -> Pre-computing ~ similar to prefix sum.

        -> we need sorting as well. 
        Why descending order? 
        we traverse left to right.

        keep track of the height (h) 
        = how many 1s above me (inc. myself)? 
        E.g.,

            [0,0,"1"]
            [1,1,"1"] <- h=2 for matrix[1][2]
        
        E.g.,
            [0,0,"1"]
            [1,1,"1"]
            [1,0,"1"] <- h=3 for matrix[2][2]
        
        Hence, for this matrix, the height of
        each cell will be
            [0,0,1]
            [1,1,2]
            [2,0,3] 

        As we iterate on a row and modify 
        matrix[row], we only depend on values 
        from the previous row matrix[row - 1].
        = prev row and current row is all we 
        need.

        In the above height matrix, consider 
        the bottom right square (2, 2). 
        The value of this square is 3 because 
        there are 3 consecutive ones in this 
        column up to this point. The bottom 
        middle square (2, 1) has a value of 
        0 because matrix[2][1] = 0, so any 
        streak "resets".

        What is the point of this modification? 
        Now, we can consider how much height 
        each column can contribute at a given 
        row. Take a look at the bottom row 
        [2, 0, 3]. What happens if we sort 
        it descending?
            [2, 0, 3] -> [3, 2, 0]

        This sorted row [3, 2, 0] is saying:
            At column 0, we have seen three 
            consecutive ones.
            At column 1, we have seen two 
            consecutive ones.
            At column 2, we have seen zero 
            consecutive ones.
        Visually, this sorted row represents 
        the following image:

            |
            |   X
            |   X   X
            |   X   X
            --------------
                3   2   0
        
        Now, let's iterate over this sorted 
        row and consider the largest 
        submatrix we can make.

            At column 0, we have a height 
            of 3. What is our base? We only 
            have one column, so the base is 
            1. Thus, we have an area of 3.
            
            At column 1, we have a height 
            of 2. What is our base? Every 
            column must have a height of 
            at least 2 for us to have a 
            valid submatrix. Because we 
            sorted descending, every column 
            to the left must have a height 
            of at least 2. Thus, we have a 
            base of 2, and an area of 
            2 * 2 = 4.
            
            At column 2, we have a height 
            of 0 and a base of 3. The area 
            is 0.

        Now, hopefully, the idea is clear: 
        at each column col, we know every 
        column to its left has a height 
        greater than or equal to the 
        current height. Thus, we can treat 
        the number of columns `col + 1` as 
        the base to form a submatrix with 
        the current height.

        For a sorted currRow, we treat 
        currRow[i] as the height and i + 1 
        as the base. The reason we are 
        allowed to sort each row is because 
        sorting each row is equivalent to 
        rearranging the columns, which we 
        are allowed to do freely.
            
        We can have the heights as the cell.
        Sort them in descending order.
        Find the max area assuming it is 
        bottom-right cell.

        Time: O(m * nlogn)
        For sorting one row = nlogn
        How many rows do we have = m

        Space: O(n)
        """
        nrows, ncols = len(matrix), len(matrix[0])

        res = 0 

        prev_heights = [0] * ncols

        # for every single cell..
        # a nested for loop with r, c:
        for r in range(nrows):
            
            # init by copying
            heights = matrix[r][:]

            for c in range(ncols):
                # update 
                if heights[c] > 0:
                    heights[c] += prev_heights[c]

            # sort the row = currRow
            sorted_h = sorted(heights, reverse=True)

            # calc the area
            for i in range(ncols):
                # area = width * height
                area = (i + 1) * sorted_h[i]
                res = max(res, area)

            # update prev_h
            # wrong to set it the sorted_h
            # we need to preserve the 
            # order..
            prev_heights = heights


        return res
39600