646. Maximum Length of Pair Chain - Explanation

1. Recursion

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        pairs.sort(key=lambda x: x[1])

        def dfs(i, j):
            if i == n:
                return 0

            res = dfs(i + 1, j)
            if j == -1 or pairs[j][1] < pairs[i][0]:
                res = max(res, 1 + dfs(i + 1, i))

            return res

        return dfs(0, -1)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        pairs.sort(key=lambda x: x[1])
        dp = [[-1] * (n + 1) for _ in range(n)]

        def dfs(i, j):
            if i == n:
                return 0
            if dp[i][j + 1] != -1:
                return dp[i][j + 1]

            res = dfs(i + 1, j)
            if j == -1 or pairs[j][1] < pairs[i][0]:
                res = max(res, 1 + dfs(i + 1, i))

            dp[i][j + 1] = res
            return res

        return dfs(0, -1)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        pairs.sort(key=lambda x: x[1])
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if pairs[j][1] < pairs[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

4. Dynamic Programming (Bianry Search)

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[0])
        dp = []

        for a, b in pairs:
            pos = bisect_left(dp, a)
            if pos == len(dp):
                dp.append(b)
            else:
                dp[pos] = min(dp[pos], b)

        return len(dp)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

5. Greedy

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda p: p[1])
        length = 1
        end = pairs[0][1]

        for i in range(1, len(pairs)):
            if end < pairs[i][0]:
                length += 1
                end = pairs[i][1]

        return length

Time & Space Complexity

Time complexity: $O(n\log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.