Watch 10 video solutions for Maximum Length of Pair Chain, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by codestorywithMIK has 21,320 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.
A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.
Return the length longest chain which can be formed.
You do not need to use up all the given intervals. You can select pairs in any order.
Example 1:
Input: pairs = [[1,2],[2,3],[3,4]] Output: 2 Explanation: The longest chain is [1,2] -> [3,4].
Example 2:
Input: pairs = [[1,2],[7,8],[4,5]] Output: 3 Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].
Constraints:
n == pairs.length1 <= n <= 1000-1000 <= lefti < righti <= 1000Problem Overview: You are given an array of pairs where each pair [a, b] represents an interval. A pair [c, d] can follow [a, b] only if b < c. The goal is to build the longest possible chain of such pairs.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
This approach models the problem similarly to the Longest Increasing Subsequence. First sort the pairs by their starting value. Then iterate through the array and compute dp[i], the maximum chain length ending at pair i. For each pair i, check all previous pairs j and extend the chain when pairs[j][1] < pairs[i][0]. The transition becomes dp[i] = max(dp[i], dp[j] + 1). This guarantees the correct answer but requires a nested loop, giving O(n²) time and O(n) extra space. It’s a good baseline when learning dynamic programming patterns.
Approach 2: Greedy with Sorting (O(n log n) time, O(1) space)
The optimal insight is that the problem behaves like activity selection. Instead of maximizing chain length with DP, sort the pairs by their ending value and always pick the pair with the earliest finishing time that can extend the chain. After sorting, iterate once through the array while tracking the end of the last chosen pair. If the current pair's start is greater than the stored end, add it to the chain and update the end pointer. Sorting costs O(n log n) and the single pass costs O(n), with constant extra space.
The greedy rule works because choosing the smallest end leaves the most room for future pairs. This mirrors classic interval scheduling problems and commonly appears in greedy interview questions involving sorting and interval selection.
Recommended for interviews: The greedy sorting approach is what interviewers usually expect. The DP solution shows you understand the LIS-style formulation, but the greedy insight demonstrates stronger algorithmic reasoning and reduces complexity from O(n²) to O(n log n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (LIS-style) | O(n²) | O(n) | When learning DP transitions or explaining the problem step‑by‑step in interviews |
| Greedy with Sorting | O(n log n) | O(1) | Optimal solution; best for large inputs and commonly expected in interviews |