<p>You are given a 2D array of integers <code>envelopes</code> where <code>envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>]</code> represents the width and the height of an envelope.</p>

<p>One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope&#39;s width and height.</p>

<p>Return <em>the maximum number of envelopes you can Russian doll (i.e., put one inside the other)</em>.</p>

<p><strong>Note:</strong> You cannot rotate an envelope.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> envelopes = [[5,4],[6,4],[6,7],[2,3]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The maximum number of envelopes you can Russian doll is <code>3</code> ([2,3] =&gt; [5,4] =&gt; [6,7]).
</pre>

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

<pre>
<strong>Input:</strong> envelopes = [[1,1],[1,1],[1,1]]
<strong>Output:</strong> 1
</pre>

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

<ul>
	<li><code>1 &lt;= envelopes.length &lt;= 10<sup>5</sup></code></li>
	<li><code>envelopes[i].length == 2</code></li>
	<li><code>1 &lt;= w<sub>i</sub>, h<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

"""

Approach 
Brute
similar to lis problem easily can solved in N**2

Better
sorting is key and based on which parameter is another imp
ex : (2,3) (5, 4) , (6, 4), (6, 7)
if simple sorting based on 1st and 2nd index in asc

if we include simply the problem is values having same 1st index in that case by default LIS : (2,3) , (5,4) , (6,4)

but that is not valid the correct is (2,3) (5, 4) (6, 7)
while including if same first values we should make sure to include the largest second value so negative sorting for second value

then since 1st index are already sorted LIS on second index's using bisect_left

TC : O(nlogn)
SC : O(n)


"""

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        
        # below is the key step
        envelopes.sort(key = lambda x:(x[0], -x[1]))
        n = len(envelopes)
        lis = []

        def bisect_left(index):

            low = 0
            high = len(lis)

            while low < high:

                mid = low + ((high-low)//2)

                if lis[mid] >= envelopes[index][1]:
                    high = mid
                
                else:
                    low = mid + 1
            
            return low

        for i in range(n):

            index = bisect_left(i)

            if index == len(lis):
                lis.append(envelopes[i][1])
            
            else:

                lis[index] = envelopes[i][1]
        
        return len(lis)

        """

        Dp based approach (N**2)

        lis = [1] * (n+1)

        for index in range(1,n):

            for prev_index in range(index):

                if env[i][0] > env[j][0] && env[i][1] > env[j][1] && 1 + lis[j] > lis[i]:
                    lis[i] = 1 + lis[j]
            
            max_lis = max(max_lis, lis[i])
        
        return max_lis

        """












        
63100