Maximum Length of Pair Chain
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as a variation of the classic Longest Increasing Subsequence (LIS) problem. The fundamental idea is to build the solution incrementally. We first sort the pairs by their starting points. Then, we use a dynamic programming array, dp, where dp[i] represents the length of the longest chain that can be formed ending with the i-th pair.
Algorithm
- Sort the
pairsarray based on the first element of each pair (left_i). - Create a
dparray of sizen(wherenis the number of pairs) and initialize all its elements to 1. - Initialize a variable
maxChainLengthto 1. - Iterate through the sorted pairs from
i = 1ton-1:- For each
pairs[i], iterate through all previous pairsjfrom0toi-1:- If
pairs[j][1] < pairs[i][0], it meanspairs[i]can followpairs[j]. - Update
dp[i]with the maximum of its current value and1 + dp[j], i.e.,dp[i] = Math.max(dp[i], 1 + dp[j]).
- If
- After the inner loop, update
maxChainLength = Math.max(maxChainLength, dp[i]).
- For each
- Return
maxChainLength.
Walkthrough
First, we sort the pairs array based on the first element of each pair. This ordering helps in building the chain, as we only need to consider previous pairs (j < i) to extend a chain ending at pairs[i].
We initialize a dp array of size n with all values set to 1. This is because any single pair constitutes a valid chain of length 1.
We then iterate through the sorted pairs from the second pair (i = 1) to the last. For each pairs[i], we look back at all preceding pairs pairs[j] (where j < i). If we find a pairs[j] such that pairs[j][1] < pairs[i][0], it means pairs[i] can follow pairs[j] to form a longer chain. We update dp[i] to be the maximum of its current value and 1 + dp[j].
After iterating through all pairs, the longest chain could end at any position i. Therefore, the final answer is the maximum value found in the dp array.
import java.util.Arrays; class Solution { public int findLongestChain(int[][] pairs) { if (pairs == null || pairs.length == 0) { return 0; } // Sort pairs based on the first element 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 maxChainLength = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // Check if pair i can follow pair j if (pairs[j][1] < pairs[i][0]) { dp[i] = Math.max(dp[i], 1 + dp[j]); } } maxChainLength = Math.max(maxChainLength, dp[i]); } return maxChainLength; }}Complexity
Time
`O(N^2)`. Sorting takes `O(N log N)`, but the nested loops for the DP calculation take `O(N^2)`, which dominates the overall complexity.
Space
`O(N)` to store the `dp` array.
Trade-offs
Pros
Relatively straightforward to understand if you are familiar with the Longest Increasing Subsequence pattern.
Guaranteed to find the optimal solution.
Cons
The
O(N^2)time complexity is less efficient than the greedy approach and may be too slow for larger constraints (though it passes for N <= 1000).
A more optimal solution can be achieved using a greedy algorithm. This approach is analogous to the classic Activity Selection Problem. The key insight is to always choose the pair that finishes the earliest. By doing so, we maximize the remaining "space" for subsequent pairs, which intuitively leads to the longest possible chain.
Algorithm
- Sort the
pairsarray in ascending order based on the second element (right_i) of each pair. - If the array is empty, return 0.
- Initialize
chainLength = 1andcurrentEnd = pairs[0][1](the end point of the first pair in the sorted list). - Iterate through the sorted
pairsarray from the second element (i = 1ton-1). - For each
pair[i], if its start point is greater than the end of the current chain (pair[i][0] > currentEnd):- This pair can extend the current chain, so increment
chainLength. - Update
currentEndto the end point of this new pair,currentEnd = pair[i][1].
- This pair can extend the current chain, so increment
- Return
chainLength.
Walkthrough
The first step is to sort the pairs array based on their end points (right_i) in ascending order. This is the crucial greedy choice. The pair that finishes first is pairs[0] after sorting.
We initialize our chain with this first pair. We set the chainLength to 1 and record the end point of this pair, currentEnd = pairs[0][1].
Then, we iterate through the rest of the sorted pairs, from i = 1 to n-1. For each pairs[i], we check if it can follow the last pair in our current chain. The condition is pairs[i][0] > currentEnd.
If the condition is met, it means we can add pairs[i] to our chain. We increment chainLength and update currentEnd to the end point of this new pair, pairs[i][1]. Since the pairs are sorted by their end points, this new currentEnd is the earliest possible end time for a chain of this new length, which is the essence of the greedy strategy.
If the condition is not met, we simply skip pairs[i] and move to the next one, as including it would break the chain.
After iterating through all pairs, chainLength will hold the length of the longest possible chain.
import java.util.Arrays;import java.util.Comparator; class Solution { public int findLongestChain(int[][] pairs) { if (pairs == null || pairs.length == 0) { return 0; } // Sort pairs based on the second element (end point) Arrays.sort(pairs, Comparator.comparingInt(a -> a[1])); int chainLength = 1; int currentEnd = pairs[0][1]; for (int i = 1; i < pairs.length; i++) { if (pairs[i][0] > currentEnd) { chainLength++; currentEnd = pairs[i][1]; } } return chainLength; }}Complexity
Time
`O(N log N)`. The dominant operation is sorting the array. The subsequent loop is a single pass, taking `O(N)` time.
Space
`O(log N)` to `O(N)`. This is the space required by the sorting algorithm. In Java, `Arrays.sort` for objects uses Timsort, which may require `O(N)` space in the worst case.
Trade-offs
Pros
Highly efficient with
O(N log N)time complexity.Simple and concise implementation.
Uses constant extra space, apart from the space used for sorting.
Cons
The correctness of the greedy choice (sorting by end time) is not immediately obvious and relies on a proof similar to that for the Activity Selection Problem.
Solutions
Solution
class Solution {public int findLongestChain(int[][] pairs) { Arrays.sort(pairs, Comparator.comparingInt(a->a[1])); int ans = 0; int cur = Integer.MIN_VALUE; for (int[] p : pairs) { if (cur < p[0]) { cur = p[1]; ++ans; } } return ans; }}class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: ans, cur = 0, - inf for a, b in sorted(pairs, key=lambda x: x[1]): if cur < a: cur = b ans += 1 return ansclass Solution {public: int findLongestChain(vector<vector<int>> &pairs) { sort(pairs.begin(), pairs.end(), [](vector<int> &a, vector<int> b) { return a[1] < b[1]; }); int ans = 0, cur = INT_MIN; for (auto &p : pairs) { if (cur < p[0]) { cur = p[1]; ++ans; } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.