Maximum Length of Pair Chain solution and explanation
Google
9 more videos on this problem
Maximum Length of Pair Chain | Same as LIS | FULL INTUITION | DP Concepts & Qns - 13 | Leetcode-646codestorywithMIK · 22:44 · 25K views
Maximum Length of Pair Chain - Leetcode 646 - PythonNeetCodeIO · 13:46 · 10K views
646. Maximum Length of Pair Chain | LEETCODE MEDIUMcode Explainer · 8:27 · 1K views
646. Maximum Length of Pair Chain LeetCode GreedyCoding Gist · 7:13 · 1K views
Maximum Length of Pair Chain | Leetcode 646Knowledge Center · 19:51 · 894 views
Length of maximum pair chain | dynamic programming | leetcode#646Joey'sTech · 7:09 · 706 views
646. Maximum Length of Pair Chain | Leetcode 26 August | #Solution # Hint #leetcodeKhushboo Goel · 1:29 · 674 views
Daily Leetcode #1243: Aug 26, 2023 - 646. Maximum Length of Pair ChainProgramming Live with Larry · 27:25 · 494 views
Unlock Your Dream Tech Job with This ONE Algorithm! | LeetCode 646 Maximum Length of Pair ChainvanAmsen · 5:15 · 490 views
Maximum Length of Pair Chain - Leetcode 646 - PythonTechError · 4:35 · 320 views
The problem
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 <= 1000
Approach overview
Problem 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 1: Greedy Approach with Sorting
This approach involves sorting the pairs by their second element and then greedily selecting pairs that can extend the chain. The intuition here is that by picking the pairs with the smallest possible ending, we maintain maximum flexibility for extending the chain.
def findLongestChain(pairs):
pairs.sort(key=lambda x: x[1])
current_end = float('-inf')
count = 0
for pair in pairs:
if pair[0] > current_end:
current_end = pair[1]
count += 1
return count
pairs = [[1, 2], [2, 3], [3, 4]]
print(findLongestChain(pairs))import java.util.*;
public class PairChain {
public static int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
int currentEnd = Integer.MIN_VALUE, count = 0;
for (int[] pair : pairs) {
if (pair[0] > currentEnd) {
currentEnd = pair[1];
count++;
}
}
return count;
}
public static void main(String[] args) {
int[][] pairs = {{1, 2}, {2, 3}, {3, 4}};
System.out.println(findLongestChain(pairs));
}
}#include <vector>
#include <algorithm>
#include <iostream>
int findLongestChain(std::vector<std::vector<int>>& pairs) {
std::sort(pairs.begin(), pairs.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
return a[1] < b[1];
});
int currentEnd = INT_MIN, count = 0;
for (const auto& pair : pairs) {
if (pair[0] > currentEnd) {
currentEnd = pair[1];
count++;
}
}
return count;
}
int main() {
std::vector<std::vector<int>> pairs = {{1,2},{2,3},{3,4}};
std::cout << findLongestChain(pairs) << std::endl;
return 0;
}function findLongestChain(pairs) {
pairs.sort((a, b) => a[1] - b[1]);
let currentEnd = Number.MIN_SAFE_INTEGER, count = 0;
for (let pair of pairs) {
if (pair[0] > currentEnd) {
currentEnd = pair[1];
count++;
}
}
return count;
}
console.log(findLongestChain([[1, 2], [2, 3], [3, 4]]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return ((int *)a)[1] - ((int *)b)[1];
}
int findLongestChain(int pairs[][2], int pairsSize) {
qsort(pairs, pairsSize, sizeof(pairs[0]), compare);
int count = 0, currentEnd = INT_MIN;
for (int i = 0; i < pairsSize; i++) {
if (pairs[i][0] > currentEnd) {
count++;
currentEnd = pairs[i][1];
}
}
return count;
}
int main() {
int pairs[][2] = {{1,2},{2,3},{3,4}};
printf("%d\n", findLongestChain(pairs, 3));
return 0;
}using System;
using System.Collections.Generic;
public class PairChain {
public static int FindLongestChain(int[][] pairs) {
Array.Sort(pairs, (a, b) => a[1].CompareTo(b[1]));
int currentEnd = int.MinValue, count = 0;
foreach (var pair in pairs) {
if (pair[0] > currentEnd) {
currentEnd = pair[1];
count++;
}
}
return count;
}
public static void Main() {
int[][] pairs = new int[][] { new int[] {1, 2}, new int[] {2, 3}, new int[] {3, 4} };
Console.WriteLine(FindLongestChain(pairs));
}
}The Python solution uses sort with a lambda function to arrange the pairs based on the second element. It then applies the greedy logic to find the longest chain of pairs.
Time Complexity: O(n log n)
Space Complexity: O(1)
Approach 2: Dynamic Programming Approach
This approach uses dynamic programming to determine the longest chain. We first sort the pairs based on the first element. Then, we define a DP array where dp[i] represents the length of the longest chain ending with the i-th pair.
def findLongestChain(pairs):
pairs.sort() # Sort by the first element of the pairs
dp = [1] * len(pairs)
max_length = 1
for i in range(1, len(pairs)):
for j in range(0, i):
if pairs[j][1] < pairs[i][0]:
dp[i] = max(dp[i], dp[j] + 1)
max_length = max(max_length, dp[i])
return max_length
pairs = [[1, 2], [2, 3], [3, 4]]
print(findLongestChain(pairs))import java.util.*;
public class PairChain {
public static int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));
int n = pairs.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
public static void main(String[] args) {
int[][] pairs = {{1, 2}, {2, 3}, {3, 4}};
System.out.println(findLongestChain(pairs));
}
}#include <vector>
#include <algorithm>
#include <iostream>
int findLongestChain(std::vector<std::vector<int>>& pairs) {
std::sort(pairs.begin(), pairs.end());
std::vector<int> dp(pairs.size(), 1);
int maxLen = 1;
for (int i = 1; i < pairs.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = std::max(dp[i], dp[j] + 1);
}
}
maxLen = std::max(maxLen, dp[i]);
}
return maxLen;
}
int main() {
std::vector<std::vector<int>> pairs = {{1, 2}, {2, 3}, {3, 4}};
std::cout << findLongestChain(pairs) << std::endl;
return 0;
}function findLongestChain(pairs) {
pairs.sort((a, b) => a[0] - b[0]);
const dp = new Array(pairs.length).fill(1);
let maxLen = 1;
for (let i = 1; i < pairs.length; i++) {
for (let j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
console.log(findLongestChain([[1, 2], [2, 3], [3, 4]]));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return ((int*)a)[0] - ((int*)b)[0];
}
int findLongestChain(int pairs[][2], int pairsSize) {
int dp[pairsSize];
for (int i = 0; i < pairsSize; ++i) {
dp[i] = 1;
}
qsort(pairs, pairsSize, sizeof(pairs[0]), compare);
int maxLen = 1;
for (int i = 1; i < pairsSize; ++i) {
for (int j = 0; j < i; ++j) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = (dp[i] > dp[j] + 1) ? dp[i] : dp[j] + 1;
}
}
maxLen = (maxLen > dp[i]) ? maxLen : dp[i];
}
return maxLen;
}
int main() {
int pairs[][2] = {{1,2},{2,3},{3,4}};
printf("%d\n", findLongestChain(pairs, 3));
return 0;
}using System;
using System.Collections.Generic;
public class PairChain {
public static int FindLongestChain(int[][] pairs) {
Array.Sort(pairs, (a, b) => a[0].CompareTo(b[0]));
int[] dp = new int[pairs.Length];
Array.Fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < pairs.Length; i++) {
for (int j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
maxLen = Math.Max(maxLen, dp[i]);
}
return maxLen;
}
public static void Main() {
int[][] pairs = new int[][] { new int[] {1, 2}, new int[] {2, 3}, new int[] {3, 4} };
Console.WriteLine(FindLongestChain(pairs));
}
}The Python implementation constructs the dp array initialized to 1. It sorts the pairs by their first element and fills in dp based on possible chains, ultimately determining the maximum length.
Time Complexity: O(n^2)
Space Complexity: O(n)
Approach 3: Sorting + Greedy
We sort all pairs in ascending order by the second number, and use a variable pre to maintain the maximum value of the second number of the selected pairs.
We traverse the sorted pairs. If the first number of the current pair is greater than pre, we can greedily select the current pair, increment the answer by one, and update pre to the second number of the current pair.
After the traversal, we return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of pairs.
function findLongestChain(pairs: number[][]): number {
pairs.sort((a, b) => a[1] - b[1]);
let [ans, pre] = [0, -Infinity];
for (const [a, b] of pairs) {
if (pre < a) {
++ans;
pre = b;
}
}
return ans;
}func findLongestChain(pairs [][]int) (ans int) {
sort.Slice(pairs, func(i, j int) bool { return pairs[i][1] < pairs[j][1] })
pre := math.MinInt
for _, p := range pairs {
if pre < p[0] {
ans++
pre = p[1]
}
}
return
}impl Solution {
pub fn find_longest_chain(mut pairs: Vec<Vec<i32>>) -> i32 {
pairs.sort_by_key(|pair| pair[1]);
let mut ans = 0;
let mut pre = i32::MIN;
for pair in pairs {
let (a, b) = (pair[0], pair[1]);
if pre < a {
ans += 1;
pre = b;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) |
| Dynamic Programming Approach | Time Complexity: O(n^2) |
| Sorting + Greedy | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximum Length of Pair Chain easy or hard?
Maximum Length of Pair Chain is rated Medium on LeetCode. The dynamic programming solution is straightforward once you recognize the LIS pattern, but identifying the optimal greedy strategy with interval sorting requires deeper algorithmic insight.
Maximum Length of Pair Chain Python/Java solution
Most implementations follow the greedy pattern: sort pairs by their second value, iterate through them, and count how many valid pairs can extend the chain. The same logic works in Python, Java, C++, C#, and JavaScript with built‑in sorting functions.
How to solve Maximum Length of Pair Chain in O(n)?
A strictly O(n) solution is not possible for unsorted input because you must determine the correct order of intervals first. The fastest practical solution is O(n log n): sort the pairs by their end value and greedily pick compatible pairs in a single pass.
What is the best approach for Maximum Length of Pair Chain?
The greedy approach with sorting is the optimal solution. Sort pairs by their ending value and always choose the next pair whose start is greater than the end of the previously selected pair. This strategy works because picking the earliest finishing pair leaves maximum room for future pairs. The time complexity is O(n log n) due to sorting and O(1) extra space.
Is Maximum Length of Pair Chain asked at Google/Amazon/Meta?
Maximum Length of Pair Chain appears in interviews at several major tech companies because it tests greedy reasoning and interval scheduling concepts. Variations of this problem have been reported in interviews at companies like Amazon, Google, and Meta, especially for roles requiring strong algorithmic fundamentals.
What data structure is used in Maximum Length of Pair Chain?
The solution primarily relies on arrays and sorting. The dynamic programming approach additionally uses a DP array to store the best chain length ending at each pair. The greedy solution only tracks the last selected interval end, so it uses constant extra space.
What is the time complexity of Maximum Length of Pair Chain?
The optimal greedy solution runs in O(n log n) time because the pairs must be sorted by their end value before scanning the array once. The dynamic programming alternative takes O(n^2) time since it checks all previous pairs for every element. Space complexity is O(1) for greedy and O(n) for the DP approach.