algoadvance

Leetcode 646. Maximum Length of Pair Chain

Problem Statement

You are given an array of n pairs pairs where pairs[i] = [start_i, end_i]. A pair (c, d) can follow another pair (a, b) if and only if b < c. A pair chain is a sequence of pairs p_1, p_2, ..., p_k with k >= 1 where p_i follows p_{i-1}.

Return the length of the longest chain which can be formed.

Example

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

Clarifying Questions

  1. What is the maximum size of the input array?
    • This would help in understanding any constraints around time and space complexity.
  2. Are the pairs always given in a sorted order?
    • This usually is not the case but confirming helps in strategizing sorting if needed.
  3. Can the pairs contain negative numbers or zero?
    • Understanding range constraints for elements helps ensure correct handling of data types.
  4. Are the pairs distinct or can they have duplicates within the array?
    • This helps to ensure proper handling, especially if duplicates are allowed.

Strategy

  1. Sort the Pairs: Sort the pairs based on the second element of each pair (i.e., end_i). This step ensures that you get the smallest possible ending first which helps in forming the longest chain.

  2. Dynamic Programming/Greedy: Use a greedy approach to build the longest chain. Initialize an end variable to the minimum possible value. Iterate through the sorted pairs and for each pair, if the starting value of the current pair is greater than the current end value, include this pair in the chain and update the end value to the ending value of this pair.

Code

Here is the C++ code implementing the proposed strategy:

#include <vector>
#include <algorithm>

int findLongestChain(std::vector<std::vector<int>>& pairs) {
    // Initialize the count of longest chain length.
    int longestChainLength = 0;
    
    // Sort the pairs based on their second elements.
    std::sort(pairs.begin(), pairs.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        return a[1] < b[1];
    });
    
    // Initialize the "end" variable to a low value.
    int currentEnd = INT_MIN;
    
    // Iterate through the sorted pairs.
    for (const auto& pair : pairs) {
        // If the current pair can be chained to the longest chain so far, update `currentEnd`.
        if (pair[0] > currentEnd) {
            currentEnd = pair[1];
            ++longestChainLength;
        }
    }
    
    // Return the maximum length of the chain.
    return longestChainLength;
}

Time Complexity

Combining both, the overall time complexity of the solution is O(n log n) due to the sorting step. The algorithm is efficient and handles larger input sizes within acceptable limits.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI