0354 Russian Doll Envelope

0354 Russian Doll Envelope#

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

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

Note: You cannot rotate an envelope.

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

1 <= envelopes.length <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105

Dynamic programming
Patience sort

def maxEnvelopes(envelopes):
    # O(N2) cannot pass due to time limit
    n = len(envelopes)

    # dp table
    dp = [1]*n

    # sort the envelopes in ascending order
    envelopes.sort(key=lambda x: (x[0], -x[1]))

    # fill dp
    for i in range(1, n):
        for j in range(i):
            if envelopes[i][0] > envelopes[j][0] and envelopes[i][1] > envelopes[j][1]:
                dp[i] = max(dp[i], dp[j]+1)
    
    return max(dp)

# test
envelopes = [[5,4],[6,4],[6,7],[2,3]]
print(maxEnvelopes(envelopes))

envelopes = [[1,1],[1,1],[1,1]]
print(maxEnvelopes(envelopes))

envelopes = [[1,1],[2,2],[3,3],[4,4],[5,5]]
print(maxEnvelopes(envelopes))

envelopes = [[1,1],[2,2],[3,3],[4,4],[5,5],[5,6],[6,7],[7,8],[8,9],[9,10]]
print(maxEnvelopes(envelopes))

# add a length 0f 10000 test case
envelopes = [[i, i] for i in range(10000)]
print(maxEnvelopes(envelopes))

def maxEnvelopes(envelopes):
    # O(nlogn) solution
    # sort the envelopes in ascending order of width, and descending order of height
    # then find the longest increasing subsequence of heights
    # the time complexity is O(nlogn) + O(nlogn) = O(nlogn)
    # the space complexity is O(n)
    n = len(envelopes)

    # sort the envelopes
    envelopes.sort(key=lambda x: (x[0], -x[1]))

    # find the longest increasing subsequence of heights
    heights = [envelope[1] for envelope in envelopes]
    dp = []
    dp.append(heights[0])

    for i in range(1, n):
        num = heights[i]
        # if num is greater than the last element in dp, append it to dp
        if num > dp[-1]:
            dp.append(num)
        # if num is smaller than the last element in dp, find the first element in dp that is greater than num using binary search
        else:
            l, r = 0, len(dp)-1
            while l < r:
                mid = l + (r-l)//2
                # if the mid element is smaller than num, search the right half
                if dp[mid] < num:
                    l = mid +1
                elif dp[mid] > num:
                    r = mid
                else:
                    # if the mid element is equal to num, search the left half because we want to find the first element that is no less than than num 
                    r = mid
            dp[l] = num

    return len(dp)

# test
envelopes = [[5,4],[6,4],[6,7],[2,3]]
print(maxEnvelopes(envelopes))

envelopes = [[1,1],[1,1],[1,1]]
print(maxEnvelopes(envelopes))

envelopes = [[1,1],[2,2],[3,3],[4,4],[5,5]]
print(maxEnvelopes(envelopes))

envelopes = [[1,1],[2,2],[3,3],[4,4],[5,5],[5,6],[6,7],[7,8],[8,9],[9,10]]
print(maxEnvelopes(envelopes))

# add a length 0f 10000 test case
envelopes = [[i, i] for i in range(10000)]
print(maxEnvelopes(envelopes))