646. Maximum Length of Pair Chain LeetCode Solution

In this guide, you will get 646. Maximum Length of Pair Chain LeetCode Solution with the best time and space complexity. The solution to Maximum Length of Pair Chain problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Length of Pair Chain solution in C++
Maximum Length of Pair Chain solution in Java
Maximum Length of Pair Chain solution in Python
Additional Resources

646. Maximum Length of Pair Chain LeetCode Solution image

Problem Statement of Maximum Length of Pair Chain

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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

646. Maximum Length of Pair Chain LeetCode Solution in C++

class Solution {
 public:
  int findLongestChain(vector<vector<int>>& pairs) {
    int ans = 0;
    int prevEnd = INT_MIN;

    ranges::sort(pairs,
                 [](const auto& a, const auto& b) { return a[1] < b[1]; });

    for (const vector<int>& pair : pairs)
      if (pair[0] > prevEnd) {
        ++ans;
        prevEnd = pair[1];
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

646. Maximum Length of Pair Chain LeetCode Solution in Java

import java.util.Arrays;

class Solution {
  public int findLongestChain(int[][] pairs) {
    int ans = 0;
    int prevEnd = Integer.MIN_VALUE;

    Arrays.sort(pairs, (a, b) -> Integer.compare(a[1], b[1]));

    for (int[] pair : pairs)
      if (pair[0] > prevEnd) {
        ++ans;
        prevEnd = pair[1];
      }

    return ans;
  }
}
// code provided by PROGIEZ

646. Maximum Length of Pair Chain LeetCode Solution in Python

class Solution:
  def findLongestChain(self, pairs: list[list[int]]) -> int:
    ans = 0
    prevEnd = -math.inf

    for s, e in sorted(pairs, key=lambda x: x[1]):
      if s > prevEnd:
        ans += 1
        prevEnd = e

    return ans
 # code by PROGIEZ