Maximum Length of Pair Chain

MEDIUM

Description

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

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 <= left_i < right_i <= 1000

Approaches

Checkout 2 different approaches to solve Maximum Length of Pair Chain. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming (LIS-based)

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 pairs array based on the first element of each pair (left_i).
Create a dp array of size n (where n is the number of pairs) and initialize all its elements to 1.
Initialize a variable maxChainLength to 1.
Iterate through the sorted pairs from i = 1 to n-1:
- For each pairs[i], iterate through all previous pairs j from 0 to i-1:
  - If pairs[j][1] < pairs[i][0], it means pairs[i] can follow pairs[j].
  - Update dp[i] with the maximum of its current value and 1 + dp[j], i.e., dp[i] = Math.max(dp[i], 1 + dp[j]).
- After the inner loop, update maxChainLength = Math.max(maxChainLength, dp[i]).
Return maxChainLength.

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 Analysis

Time Complexity: `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 Complexity: `O(N)` to store the `dp` array.

Pros and Cons

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).

Code Solutions

Checking out 3 solutions in different languages for Maximum Length of Pair Chain. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Maximum Length of Pair Chain

Algorithms:

Sorting

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

Array

Companies:

Swiggy |