Solution by awice


  • 0

    Approach #1: Brute Force [Time Limit Exceeded]

    Intuition and Algorithm

    Let A be the given array. Because the final chain has elements in sorted order, adding to our answer by considering A in sorted order must achieve the correct final result.

    Let tails[j] = k indicate that a chain ending on j has maximum length k. At each interval (j, k), we try to add it to all our current considered chains, including the chain (j, k) of length 1.

    Python

    class Solution(object):
        def findLongestChain(self, A):
            A.sort()
            tails = {float('-inf'): 0}
            for j, k in A:
                for i in tails.keys():
                    if i < j:
                        tails[k] = max(tails.get(k, 0), tails[i] + 1)
                tails[k] = max(tails.get(k, 0), 1)
            return max(tails.values())
    

    Complexity Analysis

    • Time Complexity: $$O(N^2)$$, where $$N$$ is the length of the given array. The sorting step is $$O(N \log N)$$, which is dominated by the other steps. In the rest of the code, each interval considered in the outer loop "for j, k in A", we run through an inner loop "for i in tails.keys()" with amortized complexity $$O(N)$$, which is in total $$O(N^2)$$.

    • Space Complexity: $$O(N)$$. We need $$O(N)$$ space to store intermediate results related to tails.


    Approach #2: Dynamic Programming, Naive Variation [Time Limit Exceeded]

    Intuition and Algorithm

    Again as in Approach #1, we only need to consider elements from A in sorted order.

    Let dp[i] be the length of a longest chain ending at A[i][1].

    Then, dp[i] equals $\max\limits_{j < i}(dp[j] + 1 \text{ | } A[j][1] < A[i][0])$, or dp[i] = 1 if no j exists.

    We can use bottom-up dynamic programming to calculate the answer based on this recursion.

    Python

    class Solution(object):
        def findLongestChain(self, A):
            A.sort()
            dp = [1] * len(A)
            for i in range(len(A)):
                for j in range(i):
                    if A[j][1] < A[i][0]:
                        dp[i] = max(dp[i], dp[j] + 1)
            return max(dp)
    

    Complexity Analysis

    • Time Complexity: $$O(N^2)$$, where $$N$$ is the length of the given array. The complexity comes from the two for loops in the code. The sorting step is $$O(N \log N)$$, but is dominated by the other steps.

    • Space Complexity: $$O(N)$$. We need $$O(N)$$ space to store the array dp.


    Approach #3: Dynamic Programming, Bisection Variation [Time Limit Exceeded]

    Intuition and Algorithm

    Again as in Approach #1, we only need to consider elements from A in sorted order.

    Let dp[i] be the smallest endpoint for a chain of length i. As we consider intervals in sorted order, we will maintain this invariant.

    Then, dp[i] is increasing, and whenever we see an interval (x, y) with dp[i-1] < x, we know that we can possibly extend the chain ending in dp[i-1] to the new candidate dp[i] = y.

    We can use a binary search to find the first such x. If we have a new longest chain, then instead of modifying dp[i] = y we will add y to the end of dp.

    At the end, len(dp) - 1 is the length of the largest chain we found.

    Python

    class Solution(object):
        #def bisect_left(A, x):
        #    lo, hi = 0, len(A)
        #    while lo < hi:
        #        mid = (lo + hi) // 2
        #        if A[mid] < x: lo = mid + 1
        #        else: hi = mid
        #    return lo
    
        def findLongestChain(self, A):
            dp = [float('-inf')]
            for x, y in sorted(A):
                i = bisect.bisect_left(dp, x)
                if ix == len(dp):
                    dp.append(y)
                elif y < dp[i]:
                    dp[i] = y
            return len(dp) - 1
    

    Complexity Analysis

    • Time Complexity: $$O(N\log N)$$, where $$N$$ is the length of the given array. We need to sort the array, with complexity $$O(N\log N)$$. After, we iterate through an outer loop of complexity $$O(N)$$, and our inner binary search is $$O(\log N)$$. The final complexity is $$O(N\log N + N * \log N) = O(N \log N)$$.

    • Space Complexity: $$O(N)$$. We need $$O(N)$$ space to store the array dp.


    Approach #4: Greedy [Accepted]

    Intuition

    If our current longest length chain ends in z, and we have already processed all intervals (i, j) with j < z, then we do not need to consider smaller chains, because adding to our smaller chain would not make a larger length chain, and the right endpoint would be at least z.

    Algorithm

    Sort the intervals by right-most endpoint. If we can add to our current chain, then do so. After, we return the length of our chain.

    Python

    class Solution(object):
        def findLongestChain(self, A):
            A.sort(key = lambda (x, y): y)
            right, ans = float('-inf'), 0
            for x, y in A:
                if right < x:
                    right = y
                    ans += 1
            return ans
    

    Complexity Analysis

    • Time Complexity: $$O(N\log N)$$, where $$N$$ is the length of the given array. We need to sort the array, with complexity $$O(N\log N)$$; then iterate through it with complexity $$O(N)$$. Sorting dominates the complexity.

    • Space Complexity: $$O(1)$$ in additional space complexity. We need only to store the right-most endpoint and the length of our current longest chain. (If we are not allowed to modify A, our answer would be $$O(N)$$ to store the sorted array.)


Log in to reply
 

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