Scale Engineer

Maximum Length of Pair Chain

Med
#0600Time: `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: `O(N)` to store the `dp` array.1 company
Patterns
Dynamic ProgrammingGreedy
Algorithms
Sorting
Data structures
Array
Companies
Swiggy

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

`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

`O(N)` to store the `dp` array.

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem