Maximum Length Of Pair Chain - Leetcode Solution

Problem: You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

You have to find the length of the longest chain which can be formed from the given set of pairs.

Example: Input: [[1,2], [2,3], [3,4]] Output: 2 Explanation: The longest chain is [1,2] -> [3,4]

Solution: To solve the given problem, we need to follow the following steps:

1. Sort the given pairs based on the second value of each pair.
2. Iterate through the sorted pairs and keep a variable for the count of the maximum chain length. Initially, set it to 1.
3. For each pair, check if the second value of the previous pair is less than the first value of the current pair. If yes, then increment the count of chain length and update the second value of the previous pair to the second value of the current pair.
4. Return the count of chain length.

Pseudo Code:

def findLongestChain(pairs):
    # Sort the pairs based on the second value
    pairs.sort(key=lambda x: x[1])
    
    # Set the maximum chain length to 1
    max_length = 1
    
    # Keep track of the second value of the previous pair
    prev_second_value = pairs[0][1]
    
    # Iterate through the pairs starting from the second pair
    for i in range(1, len(pairs)):
        # If the second value of the previous pair is less than the first value of the current pair
        if prev_second_value < pairs[i][0]:
            # Update the maximum chain length and the second value of the previous pair
            max_length += 1
            prev_second_value = pairs[i][1]
    
    # Return the maximum chain length
    return max_length

Time Complexity: Sorting the pairs takes O(nlogn) time. Iterating through the pairs and updating the count of chain length takes O(n) time. Hence, the overall time complexity of the algorithm is O(nlogn).

Space Complexity: We are not using any extra space in the algorithm except for the variables used for storing the count of chain length and the second value of the previous pair. Hence, the space complexity of the algorithm is O(1).

1