Maximum Length of Pair Chain — Problem & Solution
Maximum Length of Pair Chain solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Length of Pair Chain is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of n pairs where pairs[i] = [left, right] and left < right.
A pair [c, d] can follow a pair [a, b] if b < c. A chain is a sequence of pairs built this way. Return the length of the longest chain that can be formed; you need not use all the pairs, and you may reorder them freely.
Example 1
Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The chain [1,2] → [3,4].
Example 2
Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3
Example 3
Input: pairs = [[-6,9],[1,6],[8,10],[-1,4],[-6,-2],[-9,8],[-5,3],[0,3]]
Output: 3
Constraints
1 <= pairs.length <= 30-1000 <= left < right <= 1000
Hints for Maximum Length of Pair Chain
Hint 1
This is interval scheduling: sort by the right endpoint and take greedily.
Hint 2
Finishing as early as possible always leaves the most room for what comes after.
Hint 3
Track the right endpoint of the last chosen pair and accept the next pair only when its left endpoint is strictly greater.
How to solve Maximum Length of Pair Chain
Interval scheduling: sort by right endpoint and greedily take every pair whose left endpoint is strictly greater than the last chosen right endpoint.
Approach
- Sort pairs by their second element.
- Walk them with
cur = -∞; whenleft > cur, take the pair and setcur = right. - Return the count.
Why it works
Among all pairs that could go next, the one finishing earliest leaves the most room for the rest; an exchange argument shows greedy matches any optimal chain length.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- The comparison is strict —
[1,2]cannot be followed by[2,3]. - The
O(n²)LIS-style DP also works but is unnecessary.
Reference solution
Python
def findLongestChain(pairs) -> int:
ordered = sorted(pairs, key=lambda p: p[1])
count = 0
cur = float("-inf")
for left, right in ordered:
if left > cur:
count += 1
cur = right
return countJava
public static int findLongestChain(int[][] pairs) {
int[][] sorted = Arrays.copyOf(pairs, pairs.length);
Arrays.sort(sorted, new Comparator<int[]>() {
public int compare(int[] a, int[] b) { return a[1] - b[1]; }
});
int count = 0, cur = -2000000;
for (int[] p : sorted) {
if (p[0] > cur) {
count++;
cur = p[1];
}
}
return count;
}C++
int findLongestChain(vector<vector<int>>& pairs) {
vector<vector<int>> sorted = pairs;
sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int count = 0, cur = -2000000;
for (vector<int>& p : sorted) {
if (p[0] > cur) {
count++;
cur = p[1];
}
}
return count;
}JavaScript
var findLongestChain = function(pairs) {
const sorted = pairs.slice().sort(function(a, b) { return a[1] - b[1]; });
let count = 0, cur = -Infinity;
for (let i = 0; i < sorted.length; i++) {
if (sorted[i][0] > cur) {
count++;
cur = sorted[i][1];
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming