Python solution with detailed explanation


  • 0
    G

    Solution

    Russian Doll Envelopes https://leetcode.com/problems/russian-doll-envelopes/

    • Sort along x dimension in ascending order. For equal x, sort descendng order for y.
    • We do this so that we do not choose [3,4], [3,7] as a valid solution. If we make it [3,7] and [3,4], we automatically invalidate [3,4], [3,7].
    • There are two ways to sort in the above way in Python using cmp method or key method. They are illustrated in the code below.
    • Then apply LIS along y dimension.

    References
    https://discuss.leetcode.com/topic/70123/python-simple-code-inspired-by-others
    https://discuss.leetcode.com/topic/28738/java-python-binary-search-o-nlogn-time-with-explanation
    https://www.peterbe.com/plog/in-python-you-sort-with-a-tuple

    from bisect import bisect_left
    class Solution(object):
        def lengthOfLIS(self, nums):
            tails = []
            for num in nums:
                idx = bisect_left(tails, num)
                if idx == len(tails):
                    tails.append(num)
                else:
                    tails[idx] = num
            return len(tails)
            
        def maxEnvelopes(self, envelopes):
            """
            :type envelopes: List[List[int]]
            :rtype: int
            """
            if envelopes == []:
                return 0
            N = len(envelopes)
            # 2 ways of sorting
    #        envelopes.sort(cmp=lambda x,y: x[0]-y[0] if x[0] != y[0] else y[1]-x[1])
            envelopes.sort(key=lambda x:(x[0], -1*x[1]))
            return self.lengthOfLIS([e[1] for e in envelopes])
    

    Dynamic Programming

    • RDE[i]: Maximum RDE sequence ending at envelope i. Envelopes are sorted in ascending order.
    • RDE [i] = max(RDE[j]) where j is an element of [0 to i] and (envelopes[j].length < envelopes[i].length) and (envelopes[j].width < envelopes[i].width)
    class Solution(object):
        def maxEnvelopes(self, envelopes):
            """
            :type envelopes: List[List[int]]
            :rtype: int
            """
            if envelopes == []:
                return 0
            N = len(envelopes)
            envelopes.sort(key=lambda x: x[0])
            dp = [1]*len(envelopes)
            max_so_far = 1
            for i in range(1, N):
                for j in range(i):
                    if (envelopes[j][0] < envelopes[i][0]) and (envelopes[j][1] < envelopes[i][1]):
                        dp[i] = max(dp[i], dp[j]+1)
                max_so_far = max(max_so_far, dp[i])
            return max_so_far
    

    Memoization

    • RDE[i]: Maximum RDE sequence starting at envelope i. Envelopes are sorted in ascending order.
    • RDE [i] = max(RDE[j]) where j is an element of [i+1 to N-1] and (envelopes[j].length > envelopes[i].length) and (envelopes[j].width > envelopes[i].width)
    class Solution(object):
        def helper(self, envelopes, i, k, cache):
            # We are finding the longest sequence for envelope with bottom at envelope[k].
            # We know that envelopes below index i cannot be candidates at all.
            if k in cache:
                return cache[k]
            last = envelopes[k] if k >= 0 else []
            cache[k] = 0
            for idx in range(i, len(envelopes)):
                x,y = envelopes[idx][0], envelopes[idx][1]
                if not last or (x > last[0] and y > last[1]):
                    cache[k] = max(cache[k], self.helper(envelopes, idx+1, idx, cache) + 1)
            return cache[k]
        
        def maxEnvelopes(self, envelopes):
            """
            :type envelopes: List[List[int]]
            :rtype: int
            """
            cache = {}
            envelopes.sort(key = lambda x: x[0])
            return self.helper(envelopes, 0, -1, cache)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.