grid47 Exploring patterns and algorithms
Sep 3, 2024
6 min read
Solution to LeetCode 646: Maximum Length of Pair Chain Problem
You are given an array of pairs where each pair represents an interval with two integers. A pair can follow another pair if the second integer of the first pair is less than the first integer of the second pair. Your task is to determine the length of the longest chain that can be formed by linking the pairs.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of pairs, where each pair is a list of two integers [lefti, righti] with lefti < righti. The number of pairs is n.
Example: pairs = [[1, 2], [2, 3], [3, 4]]
Constraints:
• 1 <= n <= 1000
• -1000 <= lefti < righti <= 1000
Output: Return an integer representing the length of the longest chain of pairs that can be formed.
Example: 2
Constraints:
• The result will be a single integer representing the length of the longest chain.
Goal: Find the length of the longest chain that can be formed from the given pairs.
Steps:
• 1. Sort the pairs by the second value of each pair.
• 2. Iterate over the sorted pairs and greedily select the ones that can form a chain, starting with the first pair and selecting each subsequent pair where the first value is greater than the second value of the previous pair.
Goal: The input will contain valid pairs where lefti < righti for each pair.
Steps:
• The number of pairs will not exceed 1000.
• Each pair will consist of two integers where lefti < righti.
Assumptions:
• The input will always contain at least one pair.
• Input: [[1, 2], [2, 3], [3, 4]]
• Explanation: The longest chain is formed by selecting pairs [1, 2] and [3, 4], giving a chain length of 2.
Approach: The solution is based on sorting the pairs and using a greedy approach to select pairs that can form a valid chain.
Observations:
• Sorting the pairs based on their second element allows us to efficiently find the longest chain by selecting pairs that follow each other.
• A greedy approach works well here because it ensures that we always pick the next pair that can extend the chain without skipping any possible valid pairs.
Steps:
• 1. Sort the pairs based on the second element of each pair.
• 2. Initialize a variable to keep track of the last element of the selected chain.
• 3. Iterate through the sorted pairs, and for each pair, check if it can be added to the chain (i.e., the first value of the current pair is greater than the last element of the previous pair).
• 4. If the pair can be added, update the chain and increase the count.
• 5. Return the total count of the longest chain.
Empty Inputs:
• The input will always contain at least one pair.
Large Inputs:
• The solution should handle inputs up to the maximum size of 1000 pairs.
Special Values:
• Pairs that are already sorted or pairs with no possible chain need to be handled properly.
Constraints:
• Ensure that the algorithm sorts the pairs efficiently and selects the valid chain in linear time after sorting.
Defines a helper function 'cmp' that compares two pairs (a and b). It first compares the first elements of the pairs, and if they are equal, it compares the second elements. This function is used for sorting the pairs.
2 : Comparison Logic
if(a[0] == b[0]) return a[1] < b[1];
Compares the second element of the pair if the first elements are equal. This ensures that the pairs are ordered first by the first element and then by the second element.
3 : Comparison Logic
elsereturn a[0] < b[0];
If the first elements of the pairs are not equal, this part of the function ensures that pairs are sorted in increasing order of the first element.
4 : Function Definition
intfindLongestChain(vector<vector<int>>& pairs) {
Defines the main function 'findLongestChain' which takes a reference to a vector of pairs and returns an integer representing the length of the longest chain of pairs.
5 : Sorting
sort(pairs.begin(), pairs.end(), cmp);
Sorts the pairs using the 'cmp' function defined earlier. This ensures that the pairs are sorted in a way that makes it easier to find the longest chain.
6 : Variable Initialization
int n = pairs.size();
Initializes an integer 'n' with the size of the 'pairs' vector, representing the total number of pairs.
7 : Dynamic Programming Initialization
vector<int> dp(n, 1);
Declares and initializes a dynamic programming vector 'dp' with size 'n', where each element is initialized to 1. The vector will be used to store the longest chain ending at each pair.
8 : Variable Initialization
int mx =1;
Initializes the variable 'mx' to 1, which will keep track of the length of the longest chain found.
9 : Outer Loop
for(int i =0; i < n; i++) {
Starts an outer loop to iterate through each pair in the sorted 'pairs' vector.
10 : Inner Loop
for(int j =0; j < i; j++) {
Starts an inner loop to check each pair before the current pair 'i' to find a valid chain.
11 : Chain Check
if(pairs[i][0] > pairs[j][1]) {
Checks if the current pair 'i' can form a valid chain with pair 'j'. The first element of pair 'i' must be greater than the second element of pair 'j'.
12 : Dynamic Programming Update
dp[i] = max(dp[i], dp[j] +1);
If the chain condition is met, updates the dynamic programming value for pair 'i', ensuring it holds the maximum length of the chain ending at that pair.
13 : Maximum Chain Length Update
mx = max(mx, dp[i]);
Updates the variable 'mx' to store the maximum length of any chain found so far.
14 : Final Return
return mx;
Returns the length of the longest chain found.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is dominated by the sorting step.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) for storing the pairs and the result.
