LeetCode 646 - Maximum Length of Pair Chain

LeetCode Problem 646

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy, Sorting

Solution

Problem Understanding

The problem gives us an array of integer pairs, where each pair represents an interval-like relationship of the form [left, right]. Every pair satisfies the condition left < right.

We want to build the longest possible chain of pairs. A pair [c, d] can follow another pair [a, b] only if:

b < c

This condition is strict. Equality is not enough. For example, [1,2] cannot be followed by [2,3] because 2 < 2 is false.

The important detail is that the pairs can be reordered in any way. We are not restricted to the original input ordering. Our task is therefore to choose a subset of pairs and arrange them so that every adjacent pair satisfies the chaining condition.

The output is a single integer representing the maximum possible length of such a chain.

The constraints are relatively small:

• 1 <= n <= 1000
• Pair values range from -1000 to 1000

A size of 1000 is large enough that exponential brute force is impractical, but small enough that an O(n^2) dynamic programming solution is acceptable. It also allows us to consider greedy solutions after sorting.

Several edge cases are important:

• Pairs that touch but do not overlap correctly, such as [1,2] and [2,3], cannot chain because the condition is strictly <.
• Negative values are allowed, so sorting logic must work correctly for negative numbers as well.
• Multiple overlapping pairs may force us to choose carefully between short-term and long-term gains.
• A single pair input should return 1.
• Completely disjoint pairs can all be chained together.

Approaches

Brute Force Approach

A brute-force solution would try every possible subset and every possible ordering of pairs to determine whether a valid chain can be formed.

One way to think about this is as a recursive backtracking process:

• Start from each pair.
• Try appending every remaining pair that can legally follow it.
• Recursively continue building chains.
• Track the maximum chain length found.

This approach is correct because it explores every valid possibility. Eventually, the longest valid chain will be discovered.

However, this solution is extremely inefficient. The number of possible orderings grows factorially, and the recursive branching becomes enormous even for moderate input sizes. With up to 1000 pairs, this approach is completely infeasible.

Key Insight

The problem is structurally very similar to interval scheduling.

Suppose we sort pairs by their ending value. If we always choose the pair that finishes earliest, we leave as much room as possible for future pairs.

This is the same greedy principle used in classic activity selection problems:

• Choosing a pair with a smaller end value gives more opportunities for future chaining.
• Choosing a pair with a larger end value can unnecessarily block future options.

Once the pairs are sorted by their second value, we can greedily build the longest chain by always taking the next compatible pair.

This works because among all candidate pairs we could choose next, the one with the smallest ending value is always at least as good as any other choice.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Tries all possible chain combinations recursively
Optimal Greedy	O(n log n)	O(1) or O(log n)	Sort by end value and greedily select compatible pairs

Algorithm Walkthrough

Optimal Greedy Algorithm

1. Sort all pairs by their ending value.

We sort using the second element of each pair. This ensures that pairs which finish earlier are considered first. Earlier finishing pairs are more flexible because they leave more space for future pairs. 2. Initialize the chain length.

We keep a variable called chain_length to count how many pairs we include in the chain. 3. Track the end of the last chosen pair.

We maintain a variable called current_end. Initially, this can be negative infinity because no pair has been selected yet. 4. Iterate through the sorted pairs.

For each pair [left, right], check whether it can follow the previously selected pair. 5. Check the chaining condition.

If:

current_end < left

then this pair can legally extend the chain. 6. Select the pair when valid.

When the pair is compatible:

• Increment chain_length
• Update current_end = right

This means the current pair becomes the new tail of the chain. 7. Continue until all pairs are processed.

By the end of the traversal, chain_length contains the maximum possible chain size.

Why it works

The greedy strategy works because choosing the pair with the smallest ending value always preserves the largest possible future search space.

Suppose two candidate pairs can both be chosen next:

• Pair A ends earlier
• Pair B ends later

If we choose Pair A, every pair that could follow Pair B can also follow Pair A, and possibly even more pairs. Therefore, choosing the earlier-ending pair is never worse.

This greedy-choice property guarantees optimality.

Python Solution

from typing import List

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda pair: pair[1])

        chain_length = 0
        current_end = float("-inf")

        for left, right in pairs:
            if current_end < left:
                chain_length += 1
                current_end = right

        return chain_length

The implementation begins by sorting the pairs according to their ending values. This is the critical preprocessing step that enables the greedy strategy.

The variable chain_length tracks how many pairs are included in the chain. The variable current_end stores the ending value of the most recently selected pair.

During iteration, each pair is checked against the chaining rule. If the pair starts after the current chain endpoint, it is selected and becomes the new chain tail.

Because the pairs are processed in increasing order of ending value, every selected pair is the best local choice and leads to the globally optimal solution.

Go Solution

package main

import "sort"

func findLongestChain(pairs [][]int) int {
	sort.Slice(pairs, func(i, j int) bool {
		return pairs[i][1] < pairs[j][1]
	})

	chainLength := 0
	currentEnd := -1001

	for _, pair := range pairs {
		left := pair[0]
		right := pair[1]

		if currentEnd < left {
			chainLength++
			currentEnd = right
		}
	}

	return chainLength
}

The Go implementation follows the exact same logic as the Python version.

The main difference is sorting syntax. Go uses sort.Slice with a custom comparison function.

Instead of using negative infinity, the Go solution initializes currentEnd to -1001, which is safely smaller than the minimum possible input value based on the constraints.

Slices are used naturally because LeetCode represents the input as [][]int.

Worked Examples

Example 1

Input:

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

After sorting by end value:

[[1,2],[2,3],[3,4]]

Step	Current Pair	current_end Before	Can Chain?	chain_length After	current_end After
1	[1,2]	-inf	Yes	1	2
2	[2,3]	2	No	1	2
3	[3,4]	2	Yes	2	4

Final answer:

2

The chain is:

[1,2] -> [3,4]

Example 2

Input:

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

After sorting by end value:

[[1,2],[4,5],[7,8]]

Step	Current Pair	current_end Before	Can Chain?	chain_length After	current_end After
1	[1,2]	-inf	Yes	1	2
2	[4,5]	2	Yes	2	5
3	[7,8]	5	Yes	3	8

Final answer:

3

The full chain is:

[1,2] -> [4,5] -> [7,8]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Only a few variables are used, sorting may use stack space

The sorting step requires O(n log n) time. After sorting, the algorithm performs a single linear scan through the pairs.

The greedy traversal itself is O(n).

The extra space usage is constant aside from implementation-specific sorting overhead.

Test Cases

from typing import List

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda pair: pair[1])

        chain_length = 0
        current_end = float("-inf")

        for left, right in pairs:
            if current_end < left:
                chain_length += 1
                current_end = right

        return chain_length

solution = Solution()

assert solution.findLongestChain([[1, 2], [2, 3], [3, 4]]) == 2
# Basic example with overlapping middle pair

assert solution.findLongestChain([[1, 2], [7, 8], [4, 5]]) == 3
# Fully chainable after sorting

assert solution.findLongestChain([[1, 10], [2, 3], [4, 5], [6, 7]]) == 3
# Greedy must avoid large interval

assert solution.findLongestChain([[1, 2]]) == 1
# Single pair input

assert solution.findLongestChain([[-10, -5], [-4, -1], [0, 3]]) == 3
# Negative values

assert solution.findLongestChain([[1, 2], [2, 3]]) == 1
# Equality does not satisfy chaining condition

assert solution.findLongestChain([[5, 24], [15, 25], [27, 40], [50, 60]]) == 3
# Standard interval scheduling style example

assert solution.findLongestChain([[1, 100], [2, 3], [4, 5], [6, 7], [8, 9]]) == 4
# Large interval should be skipped

assert solution.findLongestChain([[9, 10], [1, 2], [3, 4], [5, 6]]) == 4
# Input order should not matter

assert solution.findLongestChain([[1, 2], [1, 2], [1, 2]]) == 1
# Duplicate intervals

Test	Why
[[1,2],[2,3],[3,4]]	Verifies strict inequality handling
[[1,2],[7,8],[4,5]]	Confirms sorting enables full chaining
[[1,10],[2,3],[4,5],[6,7]]	Ensures greedy avoids bad large interval
[[1,2]]	Smallest valid input
[[-10,-5],[-4,-1],[0,3]]	Confirms negative values work correctly
[[1,2],[2,3]]	Tests strict < condition
[[5,24],[15,25],[27,40],[50,60]]	Typical mixed overlap case
[[1,100],[2,3],[4,5],[6,7],[8,9]]	Verifies optimal skipping behavior
[[9,10],[1,2],[3,4],[5,6]]	Confirms input order independence
[[1,2],[1,2],[1,2]]	Handles duplicates correctly

Edge Cases

One important edge case is pairs that touch at boundaries but do not satisfy the strict chaining condition. For example, [1,2] and [2,3] cannot form a chain because the condition requires 2 < 2, which is false. A common mistake is using <= instead of <. The implementation explicitly checks current_end < left, which correctly enforces the strict inequality.

Another important edge case is the presence of a very large interval that overlaps many smaller intervals. For example, [1,100] may appear tempting to choose early, but doing so prevents multiple shorter compatible intervals from being chained together. The greedy strategy avoids this mistake by sorting on ending values and naturally preferring shorter-ending intervals first.

Negative numbers are also important because sorting and comparisons must work independently of sign. Inputs like [[-10,-5],[-4,-1],[0,3]] demonstrate that the algorithm correctly handles values below zero without requiring any special-case logic.

Duplicate intervals form another subtle case. If multiple identical pairs exist, only one can usually participate in the chain because their ranges overlap completely. The greedy traversal naturally handles this by selecting the first compatible interval and rejecting the rest when they fail the chaining condition.