[LeetCode] 354. Russian Doll Envelopes

 Problem : https://leetcode.com/problems/russian-doll-envelopes/

This problem equals to find the length of longest increasing subsequence on 2 dimensions.

1. Sort the array. Ascending on width and descend on height for same width.

Because [3,3] cannot be contained by [3, 4], we need to put [3,4] in front of [3,3]. Otherwise,  "[3,3], [3,4]" will be considered as a valid increasing subsequence.

2.  Find the longest increasing subsequence base on height.

Since width of envelop has been sorted in increasing order, we only need to consider height.

Time Complexity = O ( N Log N )

from functools import cmp_to_key

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        
        def lowerBound(dp, n):
            left, right = 0, len(dp)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if dp[mid] == n:
                    right = mid
                elif dp[mid] > n:
                    right = mid
                elif dp[mid] < n:
                    left = mid + 1
            
            return left
        
        def compare(a, b):
            return a[0] - b[0] if a[0] != b[0] else b[1] - a[1]
        
        envelopes.sort(key=cmp_to_key(compare))
        
        dp = []
        
        for _, h  in envelopes:
            i = lowerBound(dp, h)
            
            if i == len(dp):
                dp.append(h)
            else:
                dp[i] = h
        
        return len(dp)