Home » Technical Interview Questions » Array Interview Questions » Maximum Length of Chain Pairs

Maximum Length of Chain Pairs


Reading Time - 5 mins


Difficulty Level Hard

In the maximum length of chain pairs problem we have given n pairs of numbers, find the longest chain in which (c, d) can follow (a, b) if b < c. In the given pairs the first element is always smaller than the second.

 Example

Input

[{12, 14}, {23, 29}, {18, 41}, {30,34}]

Output

3

Explanation

Here, chain is {12, 14}, {23, 29}, {30, 34}

Approach for Maximum Length of Chain Pairs

Here we use the modified way of the longest increasing subsequence algorithm. First, we need to sort the elements such a way that the first element is always in the increasing order. Now we apply the longest increasing subsequence to the current pair of the vector. Now, compare the first element of the current and second element of the chain created. If no pairs in chain add the first pair. If the first element > second element of last in chain add an element. Else, replace. Now for more understanding see the step by step execution of the logic-

arr[] = { {12, 14}, {23, 29}, {18, 41}, {30,34} };

First, we sort the array on the basis of the first element.

arr[]  = { {12,14}, {18,41}, {23,29}, {30,34} }

Now add the elements to the chain and increase the counts of the length.

chain = { {12,14} }; //step 1;

chain = { {12,14}, {23,29}}; // step 2;

READ  Split Array Into Consecutive Subsequences

chain = { {12,14}, {23,29}, {30,34}}; //step 3;

Algorithm

a. Sort the given pairs according, to the first element increasing order.

b. Here we use modified LIS,

  • Compare the first element of the current and second element of the chain created.
  • If no pairs in chain add the first pair.
  • If the first element > second element of last in chain add an element.
  • Else, replace.

c. Finally, return the length of the chain created.

C++ Program for Maximum Length of Chain Pairs

#include <stdio.h>
#include <stdlib.h>
//pair structure
struct pair
{
  int a;
  int b;
};
 
int MaxChainLen(struct pair array[], int n)
{
   int i, j, maximum_len = 0;
   int *length_array = (int*) malloc ( sizeof( int ) * n );
   //initilize length array
   for ( i = 0; i < n; i++ )
   {
      length_array[i] = 1;
   }
   //algorithm
   for(i = 1; i < n; i++ ){
      for(j = 0; j < i; j++ )
      {
         if(array[i].a > array[j].b && length_array[i] < length_array[j] + 1)
         {
            length_array[i] = length_array[j] + 1;
         }
        }
   }
   for(i = 0; i < n; i++ )
   {
      if(maximum_len < length_array[i] )
       { 
         maximum_len = length_array[i];
       }
   }
   free( length_array );
   return maximum_len;
}
 
/* Driver program to test above function */
int main()
{
    struct pair input_array[] = {{12, 14}, {18, 41}, {23, 29}, {30, 34}};
    int size = sizeof(input_array)/sizeof(input_array[0]);
    printf("length of longest chain is: %d",MaxChainLen(input_array,size));
    return 0;
}
length of longest chain is: 3

Complexity Analysis for Maximum Length of Chain Pairs

Time Complexity

O(nlogn) where n is the number of given pairs. Here we rin two for loop which leads the time complexity to n^2.

Space Complexity

O(1) because we just use a few variables as auxiliary space.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions