Skip to main content
Talentd

Maximum Length of Pair Chain - Solution & Explanation

MediumArrayDynamic ProgrammingGreedySorting15 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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.length
  • 1 <= 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.

This C solution sorts the pairs by their second element using qsort. It then iterates through the sorted pairs, maintaining the current end of the chain. If the current start of the pair is greater than the current end, it extends the chain.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as it sorts in-place.

Try this approach in the editor →

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.

The C implementation initializes a DP array with 1, as each pair can be a chain of length 1. It sorts the pairs by the first element, then uses nested loops to populate the DP table, calculating the maximum length for each position.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n) due to the DP array.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as it sorts in-place.

Dynamic Programming Approach

Time Complexity: O(n^2)
Space Complexity: O(n) due to the DP array.

Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 SortingO(n log n)O(1)Optimal solution; best for large inputs and commonly expected in interviews

Video Solution

Maximum Length of Pair Chain | Same as LIS | FULL INTUITION | DP Concepts & Qns - 13 | Leetcode-646 • codestorywithMIK • 25,025 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Length of Pair Chain with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Increasing Subsequence

Next

Longest Non-decreasing Subarray From Two Arrays