354. Russian Doll Envelopes

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        """  tc O(NlgN)  sc O(N)
        1. sort by w asc and h by desc
        2. LIS baesd on h  
        """
        if not envelopes or len(envelopes)==1 :
            return len(envelopes)
        envelopes.sort(key = lambda x:(x[0],-x[1]))
        h = [x[1] for x in envelopes ]  #store height 
        return self.LIS2(h)
    
    
    def LIS(self,A): # poker binary 
        LIS = 0
        top = [None] * len(A)
        for a in A:
            l,r = 0, LIS
            while l < r:
                mid = l + (r-l) //2
                if top[mid] >= a:
                    r = mid 
                else:
                    l = mid + 1 
            if l == LIS :
                LIS += 1
            top[l] = a
        return LIS
    
    def LIS2(self,A):
        n = len(A)
        res = [A[0]]
        for i in range(1,n):
            if A[i] > res[-1]:
                res.append(A[i])
            else:
                l = 0 
                r = len(res) #
                while l < r :
                    m = l + (r-l)//2
                    if res[m] >= A[i]:
                        r = m 
                    else:
                        l = m + 1
                res[r] = A[i] # find insertion point for A[i]
        return len(res)