LeetCode 646: Maximum Length of Pair Chain Solution

Master LeetCode problem 646 (Maximum Length of Pair Chain), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

646. Maximum Length of Pair Chain

Medium

Array Dynamic Programming Greedy Sorting

Problem Explanation

Explanation:

To solve this problem, we can sort the pairs based on their ending values. We then iterate through the sorted pairs, keeping track of the maximum chain length we can form up to that point. We update this maximum chain length by comparing it with the previous pairs' ending values. By the end of the iteration, we will have the longest chain length that can be formed.

Sort the pairs based on the ending values.
Initialize a variable maxLength to keep track of the maximum chain length.
Iterate through the sorted pairs:
- If the current pair's start value is greater than the previous pair's end value, increment maxLength and update the previous pair's end value.
Return maxLength.

Time Complexity: O(n log n) - Sorting the pairs Space Complexity: O(1) - Constant space used

Solution Code

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[1], b[1]));
        int maxLength = 1;
        int prevEnd = pairs[0][1];
        
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > prevEnd) {
                maxLength++;
                prevEnd = pairs[i][1];
            }
        }
        
        return maxLength;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 646 (Maximum Length of Pair Chain)?

This page provides optimized solutions for LeetCode problem 646 (Maximum Length of Pair Chain) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 646 (Maximum Length of Pair Chain)?

The time complexity for LeetCode 646 (Maximum Length of Pair Chain) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 646 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 646 in Java, C++, or Python.

Back to LeetCode Solutions