LeetCode 646: Maximum Length of Pair Chain Solution in Python – A Step-by-Step Guide

What Is LeetCode 646: Maximum Length of Pair Chain?

In LeetCode 646: Maximum Length of Pair Chain, you’re given a list of pairs pairs, where each pair [x, y] represents an interval with x as the start and y as the end (x ≤ y). Your task is to find the longest chain of these pairs such that for every consecutive pair in the chain, the first pair’s end (y) is less than the second pair’s start (x). The chain doesn’t need to use all pairs, and order doesn’t matter in the input. For example, with pairs = [[1, 2], [2, 3], [3, 4]], you can chain [1, 2] → [2, 3] → [3, 4] for a length of 3. This problem tests your ability to optimize sequences of intervals.

Problem Statement

• Input:
• pairs: List of lists, each [x, y] where x ≤ y.
• Output: An integer—length of the longest possible chain.
• Rules:
• Chain: For pairs [x1, y1] and [x2, y2], y1 < x2.
• Maximize chain length.
• Pairs can be used in any order, not all need inclusion.

Constraints

• 1 ≤ pairs.length ≤ 1000.
• -10⁴ ≤ x ≤ y ≤ 10⁴.

Examples

• Input: pairs = [[1, 2], [2, 3], [3, 4]]
• Output: 3 (Chain: [1, 2] → [2, 3] → [3, 4])
• Input: pairs = [[1, 2], [7, 8], [4, 5]]
• Output: 3 (Chain: [1, 2] → [4, 5] → [7, 8])
• Input: pairs = [[1, 5]]
• Output: 1 (Single pair)

These examples set the chain—let’s solve it!

Understanding the Problem: Building the Longest Chain

To solve LeetCode 646: Maximum Length of Pair Chain in Python, we need to select pairs from a list such that each pair’s end is less than the next pair’s start, maximizing the chain length. A brute-force approach—trying all possible combinations—would be O(2^n), where n is the number of pairs, impractical for n ≤ 1000. Since pairs can be chained in any order, we can optimize with greedy or DP techniques. We’ll use:

• Best Solution (Greedy with Sorting): O(n log n) time, O(1) space—fast and efficient.
• Alternative Solution (Dynamic Programming): O(n²) time, O(n) space—systematic but slower.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy with Sorting

Why This Is the Best Solution

The greedy with sorting approach is the top choice for LeetCode 646 because it’s efficient—O(n log n) time with O(1) space—and leverages a simple insight: sorting pairs by end time allows us to greedily pick the earliest-ending pair that fits, maximizing the chain length. It fits constraints (n ≤ 1000) perfectly and is intuitive once you see the sorting trick. It’s like scheduling meetings to end as early as possible to fit more in!

How It Works

Think of this as a chain picker:

• Step 1: Sort Pairs:
• Sort pairs by end time (y) ascending, then start time (x) if tied.
• Step 2: Greedy Selection:
• Start with first pair (earliest end).
• For each next pair:
• If its start (x) > current end, add it to chain, update end.
• Step 3: Count Chain Length:
• Track number of pairs added.
• Step 4: Return Result:
• Return chain length.

It’s like a greedy scheduler—pick and chain!

Step-by-Step Example

Example: pairs = [[1, 2], [7, 8], [4, 5]]

• Step 1: Sort by end time:
• [[1, 2], [4, 5], [7, 8]].
• Step 2: Greedy chain:
• Pick [1, 2], curr_end = 2, length = 1.
• [4, 5]: 4 > 2, add, curr_end = 5, length = 2.
• [7, 8]: 7 > 5, add, curr_end = 8, length = 3.
• Step 3: Chain length = 3.
• Output: 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        # Step 1: Sort pairs by end time
        pairs.sort(key=lambda x: x[1])

        # Step 2: Greedy selection
        curr_end = float('-inf')  # Current chain's end time
        chain_length = 0

        for start, end in pairs:
            if start > curr_end:
                # Add pair to chain
                curr_end = end
                chain_length += 1

        # Step 3: Return chain length
        return chain_length

• Line 4: Sort by end time (x[1]).
• Lines 7-8: Init: Start with negative infinity end, zero length.
• Lines 10-14: Greedy:
• If start > curr_end, add pair, update end, increment length.
• Line 17: Return length.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—in-place sort.

This is like a chain builder—sort and pick!

Alternative Solution: Dynamic Programming

Why an Alternative Approach?

The dynamic programming (DP) approach builds the longest chain systematically—O(n²) time, O(n) space. It’s more thorough, checking all prior pairs for each pair, but slower and uses more memory. It’s like planning every possible chain and picking the longest!

How It Works

Picture this as a chain planner:

• Step 1: Sort pairs by start time (optional, helps clarity).
• Step 2: DP array:
• dp[i]: Longest chain ending at pair i.
• Step 3: Fill DP:
• For each i, check all j < i; if j’s end < i’s start, dp[i] = max(dp[i], dp[j] + 1).
• Step 4: Return max DP value.

It’s like a chain grower—build and extend!

Step-by-Step Example

Example: Same as above

• Step 1: Sort by start: [[1, 2], [4, 5], [7, 8]].
• Step 2: Init: dp = [1, 1, 1].
• Step 3: Fill:
• i=0: [1, 2], dp[0] = 1.
• i=1: [4, 5], 4 > 2, dp[1] = max(1, dp[0] + 1) = 2.
• i=2: [7, 8], 7 > 5, dp[2] = max(1, dp[1] + 1) = 3.
• Step 4: Max(dp) = 3.
• Output: 3.

Code for DP Approach

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        # Step 1: Sort by start time (optional)
        pairs.sort()

        # Step 2: Initialize DP array
        n = len(pairs)
        dp = [1] * n  # Each pair starts as a chain of 1

        # Step 3: Fill DP
        for i in range(1, n):
            for j in range(i):
                if pairs[j][1] < pairs[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)

        # Step 4: Return maximum chain length
        return max(dp)

• Line 4: Sort by start (optional).
• Lines 7-9: Init DP with 1s.
• Lines 12-15: Fill: Check prior pairs, extend chain.
• Line 18: Return max chain length.
• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(n)—DP array.

It’s a chain planner—thorough but slower!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(n log n) time, O(1) space, fast and elegant.
• Cons: Requires sorting intuition.
• DP (Alternative):
• Pros: O(n²) time, O(n) space, systematic.
• Cons: Slower, more space.

Greedy wins for efficiency.

Additional Examples and Edge Cases

• Input: [[1, 3], [2, 4]]
• Output: 1.
• Input: [[1, 2], [2, 3], [1, 3]]
• Output: 2.

Both handle these well.

Complexity Breakdown

• Greedy: Time O(n log n), Space O(1).
• DP: Time O(n²), Space O(n).

Greedy is optimal.

Key Takeaways

• Greedy: End-time sorting—smart!
• DP: Systematic chaining—clear!
• Chains: Pairing is fun.
• Python Tip: Sorting rocks—see Python Basics.

Final Thoughts: Chain Those Pairs

LeetCode 646: Maximum Length of Pair Chain in Python is a fun interval challenge. Greedy with sorting offers speed and simplicity, while DP provides a thorough alternative. Want more? Try LeetCode 435: Non-overlapping Intervals or LeetCode 300: Longest Increasing Subsequence. Ready to link? Head to Solve LeetCode 646 on LeetCode and build that chain today!