Python solution with detailed explanation


  • 1
    G

    Maximum Length of Pair Chain https://leetcode.com/problems/maximum-length-of-pair-chain/#/description

    LIS variant using O(N^2) time and O(N) space

    • Simply sort the array and apply LIS algorithm over it.
    class Solution:
        def findLongestChain(self, pairs):
            """
            :type pairs: List[List[int]]
            :rtype: int
            """
            pairs.sort(key = lambda x:(x[0], x[1]))
            LIS = [1]*len(pairs)
            for i in range(1, len(pairs)):
                for j in range(i):
                    LIS[i] = max(LIS[i], LIS[j]+1) if pairs[j][1] < pairs[i][0] else LIS[i]
            return LIS[-1]			
    

    O(Nlg(N)) with O(N) space solution

    from bisect import bisect_left
    class Solution:
        def findLongestChain(self, pairs):
            """
            :type pairs: List[List[int]]
            :rtype: int
            """
            pairs.sort(key = lambda x:x[0])
            tails = []
            for p in pairs:
                idx = bisect_left(tails, p[1])
                if idx == len(tails):
                    if len(tails) == 0 or (idx>=1 and p[0] > tails[idx-1]):
                        tails.append(p[1])
                else:
                    tails[idx] = p[1]
            return len(tails)
    

  • 0
    S

    Dude, where is the detailed explanation?


  • 0
    G

    @spade what part is not explained in detail?


Log in to reply
 

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