Jobs

Interviews

Discussions

Maximum Length of Pair Chain

Medium

Asked by:

More companies

33 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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

Try coding it in LeetCode

Maximum Length of Pair Chain

Medium

Asked by:

33 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within each pair, and what is the maximum number of pairs in the input array?
If there are multiple valid pair chains with the same maximum length, is any one of them acceptable, or is there a specific chain I should aim to find?
Can the input array be null or empty? If so, what should I return?
Are the pairs in the input array guaranteed to be distinct, or could there be duplicate pairs? If so, how should I handle them?
Is the chain required to be strictly increasing? In other words, can the second number of one pair be equal to the first number of the next pair in the chain?

Brute Force Solution

Approach

We want to find the longest chain of pairs that follow a specific ordering rule. The brute force approach involves checking every possible combination of pairs to see which one creates the longest valid chain. Essentially, we try everything.

Here's how the algorithm would work step-by-step:

Start by considering each pair as the potential beginning of a chain.
For each starting pair, check every other pair to see if it can be added to the end of the current chain, following the ordering rule.
If a pair can be added, extend the chain by adding it and repeat the process of checking every other available pair to see if it extends it further.
If a pair cannot be added, move onto the next possible pair.
Continue extending the chain as much as possible until no more pairs can be added to the chain.
Keep track of the length of each chain that you find.
After checking all possible starting pairs and their extensions, find the longest chain among all the chains you've discovered. That's your answer.

Code Implementation

def find_maximum_pair_chain_length_brute_force(pairs):
    maximum_chain_length = 0

    for starting_pair_index in range(len(pairs)):
        current_chain_length = find_chain_length(
            pairs, starting_pair_index, [starting_pair_index]
        )
        maximum_chain_length = max(
            maximum_chain_length, current_chain_length
        )

    return maximum_chain_length

def find_chain_length(pairs, last_pair_index, current_chain):
    maximum_length = len(current_chain)

    for next_pair_index in range(len(pairs)):
        # Ensure we dont reuse pairs in the chain
        if next_pair_index not in current_chain:

            if can_append(pairs[last_pair_index], pairs[next_pair_index]):

                # Extend the chain recursively if possible
                extended_chain = current_chain + [next_pair_index]

                chain_length = find_chain_length(
                    pairs, next_pair_index, extended_chain
                )
                maximum_length = max(maximum_length, chain_length)

    return maximum_length

def can_append(first_pair, second_pair):
    # Check if pairs can be chained
    return first_pair[1] < second_pair[0]

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach considers each pair as a potential start of a chain. For each pair, it recursively explores all possible subsequent pairs to extend the chain. In the worst case, every pair can potentially follow any other pair, leading to an exponential branching factor. Therefore, the algorithm explores all possible subsets of pairs, resulting in a time complexity of O(2^n) where n is the number of pairs.

Space Complexity

O(N^2) – The brute force approach implicitly utilizes a recursion stack. In the worst case, each pair can potentially be part of a chain starting from every other pair. This could lead to nested recursive calls where each call keeps track of the currently formed chain. The maximum depth of recursion can be proportional to the number of pairs N, and at each level, we might be storing references to other pairs, leading to a space complexity of O(N^2) where N is the number of pairs.

Optimal Solution

Approach

The goal is to find the longest possible chain of pairs where each pair follows the previous one. The key idea is to sort the pairs cleverly and then greedily pick the pairs that extend the chain as far as possible.

Here's how the algorithm would work step-by-step:

First, sort all the pairs based on their ending value, from smallest to largest.
Start with an empty chain. Pick the first pair in the sorted list and add it to the chain. This will be the first pair in your chain.
Look at the next pair in the sorted list. If the starting value of this pair is greater than the ending value of the last pair you added to the chain, then this new pair can be added to the chain (because it follows the chain rule). Add it to the chain.
Repeat the previous step, going through all the remaining pairs in the sorted list. Each time, check if the new pair can extend the chain based on the chain rule, and add it if it can.
Once you have gone through all the pairs, the length of the chain you have built is the maximum possible length.

Code Implementation

def find_longest_chain(pairs):
    # Sort pairs based on the ending value.
    pairs.sort(key=lambda pair: pair[1])

    current_chain_length = 0
    last_pair_end = float('-inf')

    for pair in pairs:
        # Check if the current pair can extend the chain.
        if pair[0] > last_pair_end:
            #The current pair extends the chain.
            current_chain_length += 1

            last_pair_end = pair[1]

    return current_chain_length

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this algorithm is sorting the input array of n pairs, which takes O(n log n) time using an efficient sorting algorithm like merge sort or quicksort. The subsequent iteration through the sorted pairs involves a single loop that examines each pair once to determine if it extends the chain. This linear scan takes O(n) time. Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(1) – The algorithm sorts the input pairs in place, meaning it modifies the original array directly without creating a new array of size N. After sorting, it only uses a constant number of variables to track the current chain's end value and the length of the chain. Therefore, the auxiliary space used is independent of the input size N and remains constant, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as there are no pairs to form a chain.
Input array with only one pair	Return 1, as a single pair is a chain of length 1.
Pairs are already sorted by their second element (optimal ordering)	The solution should still correctly identify the maximum chain length without unnecessary computations if it relies on sorting.
All pairs overlap (no chain longer than 1 possible)	The algorithm should correctly return 1.
Pairs with very large or very small integer values	Ensure the chosen data type (e.g., int) can accommodate the range of values without overflow or underflow during comparisons.
Duplicate pairs in the input	The sorting and comparison logic should handle duplicate pairs correctly, treating them as distinct elements in the decision of chain extension.
Maximum sized input array (close to memory limits)	Ensure that the space complexity of the solution remains within acceptable bounds, especially if sorting or using auxiliary data structures.
Pairs sorted in reverse order requiring full traversal and logic	The algorithm should perform correctly even if the pairs are initially in the least optimal order.

Null or empty input array

How to Handle:

Return 0, as there are no pairs to form a chain.

Input array with only one pair

How to Handle:

Return 1, as a single pair is a chain of length 1.

Pairs are already sorted by their second element (optimal ordering)

How to Handle:

The solution should still correctly identify the maximum chain length without unnecessary computations if it relies on sorting.

All pairs overlap (no chain longer than 1 possible)

How to Handle:

The algorithm should correctly return 1.

Pairs with very large or very small integer values

How to Handle:

Ensure the chosen data type (e.g., int) can accommodate the range of values without overflow or underflow during comparisons.

Duplicate pairs in the input

How to Handle:

The sorting and comparison logic should handle duplicate pairs correctly, treating them as distinct elements in the decision of chain extension.

Maximum sized input array (close to memory limits)

How to Handle:

Ensure that the space complexity of the solution remains within acceptable bounds, especially if sorting or using auxiliary data structures.

Pairs sorted in reverse order requiring full traversal and logic

How to Handle:

The algorithm should perform correctly even if the pairs are initially in the least optimal order.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within each pair, and what is the maximum number of pairs in the input array?
If there are multiple valid pair chains with the same maximum length, is any one of them acceptable, or is there a specific chain I should aim to find?
Can the input array be null or empty? If so, what should I return?
Are the pairs in the input array guaranteed to be distinct, or could there be duplicate pairs? If so, how should I handle them?
Is the chain required to be strictly increasing? In other words, can the second number of one pair be equal to the first number of the next pair in the chain?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering each pair as the potential beginning of a chain.
For each starting pair, check every other pair to see if it can be added to the end of the current chain, following the ordering rule.
If a pair can be added, extend the chain by adding it and repeat the process of checking every other available pair to see if it extends it further.
If a pair cannot be added, move onto the next possible pair.
Continue extending the chain as much as possible until no more pairs can be added to the chain.
Keep track of the length of each chain that you find.
After checking all possible starting pairs and their extensions, find the longest chain among all the chains you've discovered. That's your answer.

Code Implementation

def find_maximum_pair_chain_length_brute_force(pairs):
    maximum_chain_length = 0

    for starting_pair_index in range(len(pairs)):
        current_chain_length = find_chain_length(
            pairs, starting_pair_index, [starting_pair_index]
        )
        maximum_chain_length = max(
            maximum_chain_length, current_chain_length
        )

    return maximum_chain_length

def find_chain_length(pairs, last_pair_index, current_chain):
    maximum_length = len(current_chain)

    for next_pair_index in range(len(pairs)):
        # Ensure we dont reuse pairs in the chain
        if next_pair_index not in current_chain:

            if can_append(pairs[last_pair_index], pairs[next_pair_index]):

                # Extend the chain recursively if possible
                extended_chain = current_chain + [next_pair_index]

                chain_length = find_chain_length(
                    pairs, next_pair_index, extended_chain
                )
                maximum_length = max(maximum_length, chain_length)

    return maximum_length

def can_append(first_pair, second_pair):
    # Check if pairs can be chained
    return first_pair[1] < second_pair[0]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, sort all the pairs based on their ending value, from smallest to largest.
Start with an empty chain. Pick the first pair in the sorted list and add it to the chain. This will be the first pair in your chain.
Look at the next pair in the sorted list. If the starting value of this pair is greater than the ending value of the last pair you added to the chain, then this new pair can be added to the chain (because it follows the chain rule). Add it to the chain.
Repeat the previous step, going through all the remaining pairs in the sorted list. Each time, check if the new pair can extend the chain based on the chain rule, and add it if it can.
Once you have gone through all the pairs, the length of the chain you have built is the maximum possible length.

Code Implementation

def find_longest_chain(pairs):
    # Sort pairs based on the ending value.
    pairs.sort(key=lambda pair: pair[1])

    current_chain_length = 0
    last_pair_end = float('-inf')

    for pair in pairs:
        # Check if the current pair can extend the chain.
        if pair[0] > last_pair_end:
            #The current pair extends the chain.
            current_chain_length += 1

            last_pair_end = pair[1]

    return current_chain_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as there are no pairs to form a chain.
Input array with only one pair	Return 1, as a single pair is a chain of length 1.
Pairs are already sorted by their second element (optimal ordering)	The solution should still correctly identify the maximum chain length without unnecessary computations if it relies on sorting.
All pairs overlap (no chain longer than 1 possible)	The algorithm should correctly return 1.
Pairs with very large or very small integer values	Ensure the chosen data type (e.g., int) can accommodate the range of values without overflow or underflow during comparisons.
Duplicate pairs in the input	The sorting and comparison logic should handle duplicate pairs correctly, treating them as distinct elements in the decision of chain extension.
Maximum sized input array (close to memory limits)	Ensure that the space complexity of the solution remains within acceptable bounds, especially if sorting or using auxiliary data structures.
Pairs sorted in reverse order requiring full traversal and logic	The algorithm should perform correctly even if the pairs are initially in the least optimal order.

Null or empty input array

How to Handle:

Return 0, as there are no pairs to form a chain.

Input array with only one pair

How to Handle:

Return 1, as a single pair is a chain of length 1.

Pairs are already sorted by their second element (optimal ordering)

How to Handle:

The solution should still correctly identify the maximum chain length without unnecessary computations if it relies on sorting.

All pairs overlap (no chain longer than 1 possible)

How to Handle:

The algorithm should correctly return 1.

Pairs with very large or very small integer values

How to Handle:

Ensure the chosen data type (e.g., int) can accommodate the range of values without overflow or underflow during comparisons.

Duplicate pairs in the input

How to Handle:

The sorting and comparison logic should handle duplicate pairs correctly, treating them as distinct elements in the decision of chain extension.

Maximum sized input array (close to memory limits)

How to Handle:

Ensure that the space complexity of the solution remains within acceptable bounds, especially if sorting or using auxiliary data structures.

Pairs sorted in reverse order requiring full traversal and logic

How to Handle:

The algorithm should perform correctly even if the pairs are initially in the least optimal order.