<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>

/*
Approach 1 - Sort By Height On Each Baseline Row
Let's modify matrix so that each matrix[row][col] represents the following value: 
how many consecutive 1s are there till matrix[row] are i that in that col.
Since we can swap columns or change column order we can also sort the consecutive ones till that row descending.
Now that we have the descending order of consecutive ones for each row, max area can be found as width = no of cols till now or index and height we have found

TC- O(rows * cols *log(cols))

Approach 2 - 1 but not modify matrix
we can keep 2 vectors prev and curr to find consecutive ones instead of modifying matrix
TC - same as prev

Approach 3 - keeps height in descending order so that no sort required
If matrix[row][col] = 1, there are two scenarios:

We are currently on a consecutive streak for col. In this case, some pair with 
col must already exist in prevHeights.
We are starting a new streak for col, that is, matrix[row - 1][col] was 0. We can 
simply add (1, col) to heights.

we iterate over each (height, col) pair in prevHeights. If 
matrix[row][col] = 1, then we have the first scenario and can extend the streak. 
We add (height + 1, col) to heights. Because we assume prevHeights is sorted 
descending already, we iterate over each (height, col) pair in sorted order as 
well. When we add a pair (height + 1, col) to heights, because the increment is 
fixed at 1, heights must also be sorted.

TC - O(r*c)
SC - O(c)
*/
class Solution {
public:
//     // Approach 1
//     int largestSubmatrix(vector<vector<int>>& matrix) {
//         int m = matrix.size();
//         int n = matrix[0].size();
//         int ans = 0;
        
//         for(int i=0;i<m;i++)
//         {
//             for(int j=0;j<n;j++)
//             {
//                 if(matrix[i][j] != 0 && i > 0)
//                     matrix[i][j] += matrix[i-1][j];
//             }
            
//             vector<int> currRow = matrix[i];
//             sort(currRow.begin(), currRow.end(), greater<int>());
            
//             for(int j=0;j<n;j++)
//             {
//                 ans = max(ans, currRow[j]*(j+1));
//             }
//         }
        
//         return ans;
//     }
    
//     // Approach 2: Without modifying input
//     int largestSubmatrix(vector<vector<int>>& matrix) {
//         int m = matrix.size();
//         int n = matrix[0].size();
//         int ans = 0;
//         vector<int> prevRow(n, 0);
        
//         for(int i=0;i<m;i++)
//         {
//             vector<int> currRow = matrix[i];
//             for(int j=0;j<n;j++)
//             {
//                 if(matrix[i][j] != 0)
//                     currRow[j] += prevRow[j];
//             }
            
//             vector<int> sortedRow = currRow;
//             sort(sortedRow.begin(), sortedRow.end(), greater<int>());
            
//             for(int j=0;j<n;j++)
//             {
//                 ans = max(ans, sortedRow[j]*(j+1));
//             }
            
//             prevRow = currRow;
//         }
        
//         return ans;
//     }
    
    // Approach 3: Without sorting
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<pair<int,int>> prevHeights;
        int ans = 0;
        
        for (int row = 0; row < m; row++) {
            vector<pair<int,int>> heights;
            vector<bool> seen = vector(n, false);
            
            for (auto [height, col] : prevHeights) {
                if (matrix[row][col] == 1) {
                    heights.push_back({height + 1, col});
                    seen[col] = true;
                }
            }
            
            for (int col = 0; col < n; col++) {
                if (seen[col] == false && matrix[row][col] == 1) {
                    heights.push_back({1, col});
                }
            }
            
            for (int i = 0; i < heights.size(); i++) {
                ans = max(ans, heights[i].first * (i + 1));
            }
            
            prevHeights = heights;
        }

        return ans;
    }
};
112600