646. Maximum Length of Pair Chain - Explanation

1. Recursion

Intuition

A pair [a, b] can follow pair [c, d] in a chain only if d < a. To build the longest chain, we can use recursion to explore all possibilities: for each pair, we either include it in the chain (if valid) or skip it. Sorting by the second element helps us process pairs in an order that makes chain-building more intuitive.

Algorithm

Sort pairs by their second element (end value).
Use recursion with parameters i (current index) and j (index of the last pair added to the chain, or -1 if none).
At each step, try skipping pair i. If j is -1 or the last pair's end is less than the current pair's start, also try including pair i.
Return the maximum chain length found.

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)

Intuition

The recursive solution has overlapping subproblems since we may reach the same state (i, j) through different paths. By caching results in a 2D array, we avoid redundant computation. Each state represents the maximum chain length achievable starting from index i when the last included pair was at index j.

Algorithm

Sort pairs by their second element.
Initialize a 2D memoization array dp with -1 values.
Use the same recursive logic as before, but check dp[i][j+1] before computing. Store results before returning.
The offset j+1 handles the case where j = -1 (no previous pair selected).

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)

Intuition

We can build the solution iteratively. For each pair, we look at all previous pairs and find the longest chain that can be extended by the current pair. After sorting by end values, dp[i] represents the longest chain ending at pair i.

Algorithm

Sort pairs by their second element.
Initialize a DP array where dp[i] = 1 (each pair alone forms a chain of length 1).
For each pair i, check all previous pairs j. If pairs[j][1] < pairs[i][0], then pair i can extend the chain ending at j, so update dp[i] = max(dp[i], dp[j] + 1).
Return the maximum value in the DP array.

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 (Binary Search)

Intuition

This approach is similar to the Longest Increasing Subsequence optimization. We maintain a list where dp[i] stores the smallest end value of any chain of length i+1. When processing a new pair, we binary search to find where it can extend an existing chain. By keeping track of the smallest possible end values, we maximize opportunities for future extensions.

Algorithm

Sort pairs by their first element (start value).
Maintain a list dp where dp[i] is the smallest end value among all chains of length i+1.
For each pair [a, b], use binary search to find the position where a would be inserted (first position where dp[pos] >= a).
If pos equals dp.length, append b. Otherwise, update dp[pos] = min(dp[pos], b) to keep the smallest end value.
Return the length of dp.

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

Intuition

This problem is identical to the classic interval scheduling problem. By sorting pairs by their end values, we can greedily select pairs. The key insight is that choosing the pair with the smallest end value leaves the most room for subsequent pairs. Whenever we find a pair whose start is greater than our current chain's end, we add it to the chain.

Algorithm

Sort pairs by their second element (end value).
Initialize length = 1 and end = pairs[0][1] (start with the first pair).
Iterate through remaining pairs. If a pair's start is greater than end, increment length and update end to this pair's end value.
Return length.

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.

Common Pitfalls

Sorting by the Wrong Element

A common mistake is sorting pairs by their first element (start value) instead of the second element (end value) when using the greedy approach. Sorting by end values is crucial because it ensures we always pick the pair that leaves the most room for subsequent pairs. Sorting by start values can lead to suboptimal chains.

Using Non-Strict Inequality

The problem requires that for pair [c, d] to follow pair [a, b], we need b < c (strictly less than). Using b <= c instead will incorrectly allow pairs where the end of one equals the start of another, violating the chain condition.

Confusing with Longest Increasing Subsequence

While this problem resembles LIS, the chain condition b < c is different from the standard LIS comparison. Directly applying LIS logic without adapting for the pair structure will produce incorrect results. The binary search approach requires careful handling of which element to compare and which to store.