Maximum Length of Pair Chain

Medium
337.

Maximum Length of Pair Chain

Maximum Length of Pair Chain is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.

You are given an array of n pairs where pairs[i] = [left, right] and left < right.

A pair [c, d] can follow a pair [a, b] if b < c. A chain is a sequence of pairs built this way. Return the length of the longest chain that can be formed; you need not use all the pairs, and you may reorder them freely.

Example 1

Input
pairs = [[1,2],[2,3],[3,4]]
Output
2
Explanation
The chain [1,2] → [3,4].

Example 2

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

Example 3

Input
pairs = [[-6,9],[1,6],[8,10],[-1,4],[-6,-2],[-9,8],[-5,3],[0,3]]
Output
3

Constraints

  • 1 <= pairs.length <= 30
  • -1000 <= left < right <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function(pairs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Length of Pair Chain — Problem & Solution

Maximum Length of Pair Chain solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Length of Pair Chain is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.

Problem statement

You are given an array of n pairs where pairs[i] = [left, right] and left < right.

A pair [c, d] can follow a pair [a, b] if b < c. A chain is a sequence of pairs built this way. Return the length of the longest chain that can be formed; you need not use all the pairs, and you may reorder them freely.

Example 1

Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The chain [1,2] → [3,4].

Example 2

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

Example 3

Input: pairs = [[-6,9],[1,6],[8,10],[-1,4],[-6,-2],[-9,8],[-5,3],[0,3]]
Output: 3

Constraints

  • 1 <= pairs.length <= 30
  • -1000 <= left < right <= 1000

Hints for Maximum Length of Pair Chain

  1. Hint 1

    This is interval scheduling: sort by the right endpoint and take greedily.

  2. Hint 2

    Finishing as early as possible always leaves the most room for what comes after.

  3. Hint 3

    Track the right endpoint of the last chosen pair and accept the next pair only when its left endpoint is strictly greater.

How to solve Maximum Length of Pair Chain

Interval scheduling: sort by right endpoint and greedily take every pair whose left endpoint is strictly greater than the last chosen right endpoint.

Approach

  1. Sort pairs by their second element.
  2. Walk them with cur = -∞; when left > cur, take the pair and set cur = right.
  3. Return the count.

Why it works

Among all pairs that could go next, the one finishing earliest leaves the most room for the rest; an exchange argument shows greedy matches any optimal chain length.

Complexity

  • Time — O(n log n)
  • Space — O(1) beyond the sort

Pitfalls

  • The comparison is strict — [1,2] cannot be followed by [2,3].
  • The O(n²) LIS-style DP also works but is unnecessary.

Reference solution

Python

def findLongestChain(pairs) -> int:
    ordered = sorted(pairs, key=lambda p: p[1])
    count = 0
    cur = float("-inf")
    for left, right in ordered:
        if left > cur:
            count += 1
            cur = right
    return count

Java

public static int findLongestChain(int[][] pairs) {
    int[][] sorted = Arrays.copyOf(pairs, pairs.length);
    Arrays.sort(sorted, new Comparator<int[]>() {
        public int compare(int[] a, int[] b) { return a[1] - b[1]; }
    });
    int count = 0, cur = -2000000;
    for (int[] p : sorted) {
        if (p[0] > cur) {
            count++;
            cur = p[1];
        }
    }
    return count;
}

C++

int findLongestChain(vector<vector<int>>& pairs) {
    vector<vector<int>> sorted = pairs;
    sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });
    int count = 0, cur = -2000000;
    for (vector<int>& p : sorted) {
        if (p[0] > cur) {
            count++;
            cur = p[1];
        }
    }
    return count;
}

JavaScript

var findLongestChain = function(pairs) {
    const sorted = pairs.slice().sort(function(a, b) { return a[1] - b[1]; });
    let count = 0, cur = -Infinity;
    for (let i = 0; i < sorted.length; i++) {
        if (sorted[i][0] > cur) {
            count++;
            cur = sorted[i][1];
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming