#646

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Length of Pair Chain

Determine the maximum length of a chain formed by pairs using dynamic programming and greedy sorting techniques efficiently.

array dynamic programming greedy sorting

Problem Statement

You are given an array of n pairs where each pair is [lefti, righti] and lefti < righti. A pair p2 = [c, d] can follow p1 = [a, b] if b < c. Form a chain of such pairs by connecting following pairs sequentially.

Return the length of the longest possible chain that can be formed from the given pairs. Ensure that each pair is only used once and that the chain respects the order condition b < c for consecutive pairs.

Examples

Example 1

Input: pairs = [[1,2],[2,3],[3,4]]

Output: 2

The longest chain is [1,2] -> [3,4].

Example 2

Input: pairs = [[1,2],[7,8],[4,5]]

Output: 3

The longest chain is [1,2] -> [4,5] -> [7,8].

Constraints

n == pairs.length
1 <= n <= 1000
-1000 <= lefti < righti <= 1000

Solution Approach

Sort pairs by right element

Begin by sorting all pairs based on their second value. Sorting ensures the greedy selection of pairs can extend the chain without violating the b < c constraint. This ordering simplifies the chain extension and reduces unnecessary comparisons.

Dynamic programming table

Create a DP array where dp[i] represents the longest chain ending at pair i. For each pair i, check all previous pairs j and update dp[i] if pairs[j][1] < pairs[i][0]. This uses the state transition dynamic programming pattern directly tied to this problem.

Greedy chain extension

After sorting, maintain a variable for the current chain end. Iterate through pairs and extend the chain only when the current pair starts after the last chain end. This reduces time complexity to O(n log n) while still respecting pair ordering.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n). DP evaluation can be O(n^2) if checking all previous pairs, but greedy chain extension after sorting runs in O(n). Space complexity is O(n) for DP array or O(1) for greedy tracking.

What Interviewers Usually Probe

Focus on sorting pairs by the second element to simplify chain selection.
Expect a DP or greedy approach based on the state transition dynamic programming pattern.
Be prepared to discuss time vs space trade-offs between O(n^2) DP and O(n log n) greedy solution.

Common Pitfalls or Variants

Common pitfalls

Failing to sort pairs first can lead to incorrect chain lengths.
Incorrectly updating DP table without checking b < c condition.
Mixing up greedy selection order can produce invalid chains.

Follow-up variants

Compute the longest decreasing chain by reversing pair comparisons.
Allow overlapping chains and count maximum compatible subsets instead of strict chains.
Extend to 3D triplets where each subsequent element must be larger in all dimensions.

FAQ

What is the main pattern used in Maximum Length of Pair Chain?

The problem primarily uses state transition dynamic programming, combined with greedy sorting to efficiently build the longest chain.

Can this problem be solved without dynamic programming?

Yes, a greedy approach after sorting by the second element can achieve O(n log n) time while maintaining correctness.

What common mistakes should I avoid?

Do not skip sorting, forget the b < c condition, or incorrectly extend chains without tracking the last end.

What is the time complexity for the DP approach?

Sorting is O(n log n), and evaluating all previous pairs in DP makes it O(n^2). Greedy reduces evaluation to O(n).

How do I track the longest chain efficiently?

Maintain either a DP array for state transitions or a single variable for the last chain end during greedy iteration.

terminal

Solution

Solution 1: Sorting + Greedy

We sort all pairs in ascending order by the second number, and use a variable $\textit{pre}$ to maintain the maximum value of the second number of the selected pairs.

1

2

3

4

5

6

7

8

9

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[1])
        ans, pre = 0, -inf
        for a, b in pairs:
            if pre < a:
                ans += 1
                pre = b
        return ans

Continue Practicing

#435 non overlapping intervals #1262 greatest sum divisible by three #1363 largest multiple of three