Monthly Archives: February 2016

Replace every element with the greatest element on right side in an array

Replace every element with the greatest element on right side in an array

In this post we solve the problem to replace every element with the greatest element on right side in an array.

Replace every element with the greatest element on right side in an array problem statement:

Given an array of integers,we need to replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element,we have to  replace it with -1.
Greatest element on the right side means  the element of the array which is on the right side of the given element and is the greatest number .

Replace every element with the greatest element on right side in an array problem Example:

Let the input array be 
arr[] = { 5, 8, 12, 10, 4, 6 }
Output array = { 12, 12, 10, 6, 6, -1}
arr[0] = 12 as it is the greatest on the right.
arr[3] = 6 as it is the greatest on the right of 10 .

Replace every element with the greatest element on right side in an array problem Solution:

Method 1: Simple

In this method we make use of two loops. The outer loop traverses the array one by one and the inner loop finds the greatest element in the array present after the picked element. The outer loop finally replaces the traversed element by the greatest element found by the inner loop.

Algorithm:

  1. Pick elements one by one using outer loop.
  2. Search for greatest element in array after the picked element using inner loop.
  3. Swap both the elements using outer loop.

How to replace every element with the greatest element on right side in an array problem Solution working code in C++:

#include <bits/stdc++.h>
using namespace std;

/*Function to print the elements of the array*/
void printArray(int arr[] ,int n)
{
 for(int i = 0;i < n;i++)
   cout<<arr[i]<<" ";
}

/*Function to print the modified array after replacing
   every element with the greatest on it's right */
void NextGreatest(int arr[], int n)
{
 int max;
 
 /*Outer loop for picking elements*/
 for(int i = 0;i < n;i++)
 {
    max = 0 ;
 
   /*Inner loop for finding greatest on right*/
    for(int j = i+1;j < n;j++)
    {
       if(arr[j] > max)
       max = arr[j];
    }
    int temp = arr[i];
    arr[i] = max; 
 }
 arr[n-1] = -1;//Changing last element to -1 
 cout<<"\nThe modified array is: ";
 printArray(arr , n);
}

/* Driver program to test above function */
int main()
{
  int arr[] = {5, 8, 12, 10, 4, 6};
  int size = sizeof(arr)/sizeof(arr[0]);
  cout<<"Given array :";
  printArray(arr,size);
  NextGreatest (arr, size);
  return 0;
}

 Output:

Given array :5 8 12 10 4 6 
The modified array is: 12 12 10 6 6 -1

Time Complexity:O(N*N)
Space Complexity:O(1)


Method 2: Tricky

In this method we replace all elements using one traversal of the array. The idea is to start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element.

Algorithm:

  1. Start from the rightmost element.
  2. Move towards left one by one.
  3. Replace every element with the maximum element.

Working code in C++on How to replace every element with the greatest element on right side in an array problem :

#include <bits/stdc++.h>
using namespace std;

/*Function to print the elements of an array */
void printArray(int arr[], int n)
{
  for (int i = 0; i < n; i++)
    cout<<arr[i]<<" ";
}

/*Function to print the modified array after replacing
   every element with the greatest on it's right */
void NextGreatest(int arr[], int n)
{
  /* Initialize the next greatest element */
  int max_from_right =  arr[n-1];
 
  /* The next greatest element for the rightmost element
      is always -1 */
  arr[n-1] = -1;
 
  /*Replace all other elements with the next greatest*/
  for(int i = n-2; i >= 0; i--)
  {
    /* Store the current element (needed later for updating
        the next greatest element)*/
    int temp = arr[i];
 
    /* Replace current element with the next greatest*/
    arr[i] = max_from_right;
 
    /* Update the greatest element, if needed*/
    if(max_from_right < temp)
       max_from_right = temp;
  }
}
 
/* Driver program to test above function */
int main()
{
  int arr[] = { 5, 8, 12, 10, 4, 6 };
  int size = sizeof(arr)/sizeof(arr[0]);
  cout<<"Given Array: ";
  printArray(arr, size);
  NextGreatest (arr, size);
  cout<<"\nThe modified array is: ";
  printArray (arr, size);
  return (0);
}

Output:

Given array :5 8 12 10 4 6 
The modified array is: 12 12 10 6 6 -1

Time Complexity:O(N)
Space Complexity:O(1)

Floor and Ceil in a Binary Search Tree

Floor and Ceil in a Binary Search Tree

Problem statement to find Floor and Ceil in a Binary Search Tree (BST).

In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively. More precisely, floor(x) = is the largest integer not greater than x and ceiling(x) = is the smallest integer not less than x.

Given a binary search tree (BST), we need to determine floor and ceil value of a key.

Example for finding Floor and Ceil in a Binary Search Tree (BST):

Input: 
                7
             /     \
            5        10
          /   \     /   \
         3     6   8     12
Output:
Ceil of 9 is 10
floor of 9 is 8

Solution to determine floor and ceil of a key in a binary search tree:

According to binary search tree (BST) property, elements of left subtree must be smaller than the root and elements of right subtree must be greater than the root.

If the key is less than the value at the root of a BST then floor of key must be in the left subtree. If key is greater than the key at the root then floor of key could be in the right subtree, but only if there is a key smaller than or equal to key in the right subtree; If not then the key at the root is floor of the key.

Similarly for ceil, If the key is greater than the value at the root of a BST then ceil of key must be in the right subtree. If key is less than the key at the root then floor of key could be in the left subtree, but only if there is a value greater than or equal to key in the left subtree; If not then the key at the root is ceil of the key.


TO FIND CEIL OF A KEY:

Algorithm to find the ceil of a key in a binary search tree (BST):

  1. Start at the root node.
  2. If root->data == key , then ceil of the key is equal to the root.
  3. Else if root->data < key, then ceil of the key must lie in the right subtree.
  4. Else ceil may lie in the left subtree but only if there is a value greater than or equal to the key.If not, then root is the key.

Solution code in C++ to find Ceil in a Binary Search Tree(BST):

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This funciton is used to Insert
 new values in BST*/
node *Insert(node *root,int key)
{
   if(!root)
      return newNode(key);
   if(key<root->data)	
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}

/*This function is used to find ceil of a key*/
int ceil(node *root, int key)
{
   if(!root)
      return -1;
   
   /*If root->data is equal to key*/
   if(root->data == key)
   		return root->data;
   		
   /*If root->data is less than the key*/
   if(root->data < key)
   		return ceil(root->right, key);
   		
   /*Else, the ceil may lie in left subtree
   or may be equal to the root*/ 
   int ceilValue = ceil(root->left, key);
   return (ceilValue >= key) ? ceilValue : root->data;
}

int main() {
   /* Let us create following BST
              7
            /    \
           5      10
         /  \    /  \
        3    6   8   12 */
    node *root = NULL;
    root = Insert(root, 7);
    Insert(root, 10);
    Insert(root, 5);
    Insert(root, 3);
    Insert(root, 6);
    Insert(root, 8);
    Insert(root, 12);
 
 	for(int i=0; i<16; i++)
 	{
 		cout<<i<<" -> "<<ceil(root,i)<<endl;
 	}
   return 0;
}

OUTPUT:

0 -> 3
1 -> 3
2 -> 3
3 -> 3
4 -> 5
5 -> 5
6 -> 6
7 -> 7
8 -> 8
9 -> 10
10 -> 10
11 -> 12
12 -> 12
13 -> -1
14 -> -1
15 -> -1

 Time Complexity:O(n)


TO FIND FLOOR OF A KEY:

Algorithm to find the floor of a key in a binary search tree (BST):

  1. Start at the root node.
  2. If root->data == key , then floor of the key is equal to the root.
  3. Else if root->data > key, then ceil of the key must lie in the left subtree.
  4. Else floor may lie in the right subtree but only if there is a value lesser than or equal to the key.If not, then root is the key.

Solution code in C++ to find Floor in a Binary Search Tree(BST):

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This funciton is used to Insert
 new values in BST*/
node *Insert(node *root,int key)
{
   if(!root)
      return newNode(key);
   if(key<root->data)	
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*This function is used to find floor of a key*/
int floor(node *root, int key)
{
   if(!root)
      return INT_MAX;
   
   /*If root->data is equal to key*/
   if(root->data == key)
   		return root->data;
   		
   /*If root->data is greater than the key*/
   if(root->data > key)
   		return floor(root->left, key);
   		
   /*Else, the floor may lie in right subtree
   or may be equal to the root*/ 
   int floorValue = floor(root->right, key);
   return (floorValue <= key) ? floorValue : root->data;
}

int main() {
   /* Let us create following BST
              7
            /    \
           5      10
         /  \    /  \
        3    6   8   12 */
    node *root = NULL;
    root = Insert(root, 7);
    Insert(root, 10);
    Insert(root, 5);
    Insert(root, 3);
    Insert(root, 6);
    Insert(root, 8);
    Insert(root, 12);
 
 	for(int i=3; i<16; i++)
 	{
 		cout<<i<<" -> "<<floor(root,i)<<endl;
 	}
   return 0;
}

OUTPUT:

3 -> 3
4 -> 3
5 -> 5
6 -> 6
7 -> 7
8 -> 8
9 -> 8
10 -> 10
11 -> 10
12 -> 12
13 -> 12
14 -> 12
15 -> 12

Time Complexity:O(n)

Four Elements that sum to a Given Value in an Array

Four Elements that sum to a Given Value in an Array

In this post we deal with the problem of finding four elements that sum to a given value in an array.

Four Elements that sum to a Given Value in an Array Problem Statement :

Given an array of integers, we need to find all combination of four elements in the array whose sum is equal to a given value X.
This problem can be solved using various methods.

Four Elements that sum to a Given Value in an Array Problem Example :

Let the input array be arr[] = { 2, 3, 4, 5, 8, 10 }
Let the number be X = 18
Output = { 2, 3, 5, 8 }

Four Elements that sum to a Given Value in an Array Problem Solution :

Method 1: Brute Force 

In this method we use a brute force solution to solve the problem. We generate all possible quadruples and compare the sum of every quadruple with X.

Algorithm:

  1. Fix the first elements and find other three.
  2. Fix the second element and find other two.
  3. Fix the third element and find the fourth.

Four Elements that sum to a Given Value in an Array Problem Solution Working code in C++:

#include <bits/stdc++.h>
using namespace std;

/* A solution to print all combination of 4 elements
     in arr[]  with sum equal to X */
void FindFourElements(int arr[], int n, int X)
{
  // Fix the first element and find other three
  for (int i = 0; i < n-3; i++)
  {
    // Fix the second element and find other two
    for (int j = i+1; j < n-2; j++)
    {
      // Fix the third element and find the fourth
      for (int k = j+1; k < n-1; k++)
      {
        // find the fourth
        for (int l = k+1; l < n; l++)
           if (arr[i] + arr[j] + arr[k] + arr[l] == X)
           {
              cout<<arr[i]<<" "<<arr[j]<<" "<<arr[k];
              cout<<arr[l];
           }
      }
    }
  }
}
 
// Driver program to test above funtion
int main()
{
    int arr[] = {2, 3, 4, 5, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int X = 18;
    FindFourElements (arr, n, X);
    return 0;
}

Output:

2 3 5 8

Time Complexity:O(N4)
Space Complexity:O(1)


Method 2: Sorting

In this method we first use sorting to sort the input array first and then use the first method . This reduces one loop and in turn results in less time complexity.

Algorithm:

  1. Sort the input array.
  2. Fix the first element as arr[i] where i is from 0 to n–3. After fixing the first element of quadruple, fix the second element as arr[j] where j varies from i+1 to n-2. Find remaining two elements in O(n) time, using the method 1 of post.

Find Four Elements that sum to a Given Value in an Array Problem Solution working code in C++ :

#include <bits/stdc++.h>
using namespace std;

/* A solution to print all combination of 4
    elements in arr[]  with sum equal to X */
void FindFourNumbers(int arr[], int n, int X)
{
    int l, r;
 /* Sort the elements using bubble sort*/
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < n - i - 1; ++j)
      if (arr[j] > arr[j + 1])
     {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
 
 
    /* Now fix the first 2 elements one by one and find
       the other two elements */
    for (int k = 0; k < n - 3; k++)
    {
        for (int m = k+1; m < n - 2; m++)
        {
            /* Initialize two variables as indexes of the first 
             and last elements in the remaining elements */
            l = m + 1;
            r = n-1;
 
            /* To find the remaining two elements, move the 
            index variables (l & r) toward each other.*/
            while (l < r)
            {
                if( arr[k] + arr[m] + arr[l] + arr[r] == X)
                {
                   cout<<arr[k]<<" "<<arr[m]<<" "<<arr[l];
                   cout<<arr[r];
                   l++; 
                   r--;
                }
                else if (arr[k] + arr[m] + arr[l] + arr[r] < X)
                    l++;
                else 
                    r--;
            } // end of while
        } // end of inner for loop
    } // end of outer for loop
}
 
/* Driver program to test above function */
int main()
{
    int arr[] = {2, 3, 4, 5, 8, 10};
    int X = 18;
    int n = sizeof(arr)/sizeof(arr[0]);
    FindFourNumbers(arr, n, X);
    return 0;
}

Output:

2 3 5 8

Time Complexity:O(N3)
Space Complexity:O(1)


Method 3: Auxiliary Array

In this method we create an auxiliary array aux[] and store the sum of all pairs in this array. Next we sort the array aux[] and the problem reduces to finding two elements whose sum is X.

Algorithm:

  1. Create an auxiliary array aux[] and store sum of all possible pairs in aux[]. The size of aux[] will be n*(n-1)/2 where n is the size of arr[].
  2. Sort aux[].
  3. Now the problem reduces to find two elements in aux[] with sum equal to X.

Note: An element of aux[] represents a pair from arr[]. While picking two elements from aux[], we must check whether the two elements have an element of arr[] in common. For example, if first element sum of arr[1] and arr[2], and second element is sum of arr[2] and arr[4], then these two elements of aux[] don’t represent four distinct elements of input array arr[].

Four Elements that sum to a Given Value in an Array Problem Solution Working code in C++:

#include <bits/stdc++.h>
using namespace std;

/*The following structure is needed to store pair sums in aux[]*/
struct pairSum
{
    int first; // index (int A[]) of first element in pair
    int sec; // index of second element in pair
    int sum;  // sum of the pair
};
 

/* Function to check if two given pairs have any common element or not*/
bool noCommon(pairSum a, pairSum b)
{
    if (a.first == b.first || a.first == b.sec ||
            a.sec == b.first || a.sec == b.sec)
        return false;
    return true;
}
 
 
/*Function to find four elements with given sum X*/
void findFourElements (int arr[], int n, int X)
{
    int i, j;
 
    // Create an auxiliary array to store all pair sums
    int size = (n*(n-1))/2;
    pairSum aux[size];
 
    /* Generate all possible pairs from A[] and store sums
       of all possible pairs in aux[] */
    int k = 0;
    for (i = 0; i < n-1; i++)
    {
        for (j = i+1; j < n; j++)
        {
            aux[k].sum = arr[i] + arr[j];
            aux[k].first = i;
            aux[k].sec = j;
            k++;
        }
    }
 
    /* Sort the elements using bubble sort*/
    for (int a = 0; a < n; ++a)
    for (int b = 0; b < n - a - 1; ++b)
      if (aux[b].sum > aux[b + 1].sum)
     {
        int temp = aux[b].sum;
        aux[b].sum = aux[b + 1].sum;
        aux[b + 1].sum = temp;
      }
 
    /* Now start two index variables from two corners of
       array and move them toward each other.*/
    i = 0;
    j = size-1;
    while (i < size && j >=0 )
    {
        if((aux[i].sum+aux[j].sum==X) && noCommon(aux[i],aux[j]))
        {
            cout<<arr[aux[i].first]<<" "<< arr[aux[i].sec];
            cout<<arr[aux[j].first]<<" "<<arr[aux[j].sec];
            return;
        }
        else if (aux[i].sum + aux[j].sum < X)
            i++;
        else
            j--;
    }
}
 
// Driver program to test above function
int main()
{
    int arr[] = {2, 3, 4, 5, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int X = 18;
    findFourElements (arr, n, X);
    return 0;
}

 Output:

2 3 5 8

Time Complexity:O(N2logN)
Space Complexity:O(N2)

 The step 1 takes O(N2) time. The second step is sorting an array of size O(N2). Sorting can be done in O(N2Logn) time using merge sort or heap sort or any other O(nLogn) algorithm. The third step takes O(N2) time. So overall complexity is O(N2Logn).

Count Smaller Elements on the Right in an array

Count Smaller Elements on the Right in an array

In this post we solve the problem of how to count smaller elements on the right in an array .

Count Smaller Elements on the Right in an array problem Statement :

Given an unsorted array arr[] of distinct integers, we need to construct another array CountSmaller[] such that CountSmaller[i] contains count of smaller elements on right side of each element arr[i] in array. Basically, we need to write a function to count number of smaller elements on right of each element in an array.We solve this problem using two methods as described below .

Count Smaller Elements on the Right in an array problem Example:

Example 1:
Let the input array be arr[] = { 4, 7, 12, 9, 10, 2 }
Output array CountSmaller[] = { 1, 1, 3, 1, 1, 0 }
Example 2:
Let the input array be arr[] = { 1, 2, 3, 4, 5, 6 }
Output array CountSmaller[] = { 0, 0, 0, 0, 0, 0 }

Count Smaller Elements on the Right in an array problem Solution:

Method 1:Simple

In this method we use two loops. The outer loop picks all elements from left to right. The inner loop iterates through all the elements on right side of the picked element and updates CountSmaller[].

Algorithm:

  1. Use two loops.
  2. Outer loop picks element one by one.
  3. Inner loop iterates through elements on right side of picked element.
  4. Inner loop updates CountSmaller[].

How to Count Smaller Elements on the Right in an array problem Solution Working Code in C++:

#include <bits/stdc++.h>
using namespace std;

/*Function to count smaller elements 
on the right in the given array*/
void ConstructSmallerArray(int arr[],int CountSmaller[],int n)
{
  int i, j;
 
  // initialize all the counts in countSmaller array as 0
  for  (i = 0; i < n; i++)
     CountSmaller[i] = 0;
 
/*Outer loop to pick elements from left to right*/
  for (i = 0; i < n; i++)
  {
   /*Inner loop to update CounSmaller[]*/
    for (j = i+1; j < n; j++)
    {
       if (arr[j] < arr[i])
         CountSmaller[i]++;
    }
  }
}
 
/* Function that prints out an array on a line */
void printArray(int arr[], int n)
{
  for (int i=0; i < n; i++)
    cout<<arr[i]<<" ";
}
 
/* Driver program to test above functions */
int main()
{
  int arr[] = {4, 7, 12, 9, 10, 2};
  int n = sizeof(arr)/sizeof(arr[0]);
  int low[n];
  cout<<"Input Array: ";
  printArray(arr,n);
  cout<<"\nOutput Array :";
  ConstructSmallerArray(arr, low, n);
  printArray(low, n);
  return 0;
}

 Output:

Input Array: 4 7 12 9 10 2 
Output Array :1 1 3 1 1 0

Time Complexity:O(N2)
Space Complexity:O(1)


Method 2: Using Self Balancing BST

A Self Balancing Binary Search Tree (AVL, Red Black,.. etc) can be used to get the solution in O(nLogn) time complexity. We can augment these trees so that every node N contains size the subtree rooted with N. We have used AVL tree in the following implementation.

We traverse the array from right to left and insert all elements one by one in an AVL tree. While inserting a new key in an AVL tree, we first compare the key with root. If key is greater than root, then it is greater than all the nodes in left subtree of root. So we add the size of left subtree to the count of smaller element for the key being inserted. We recursively follow the same approach for all nodes down the root.

Algorithm:

  1. Traverse the array from left to right.
  2. Insert elements in an AVL tree.
  3. Compare the key with root.
  4. If key > root ,it is greater than all nodes in left subtree.
  5. Add size of left subtree to count of smaller element for the inserted key.
  6. Use recursion for all the nodes down the root.

 Counting Smaller Elements on the Right in an array problem Solution Working Code in C++:

#include <bits/stdc++.h>
using namespace std;

// An AVL tree node
struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
    int size; // size of the tree rooted with this node
};
 
// A utility function to get maximum of two integers
int max(int a, int b);
 
// A utility function to get height of the tree rooted with N
int height(node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
// A utility function to size of the tree of rooted with N
int size(node *N)
{
    if (N == NULL)
        return 0;
    return N->size;
}
 
// A utility function to get maximum of two integers
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
/* Helper function that allocates a new node with the given
    key and NULL left and right pointers. */
 node* newNode(int key)
{
    node* Node = new node;
    Node->key   = key;
    Node->left   = NULL;
    Node->right  = NULL;
    Node->height = 1;  // new node is initially added at leaf
    Node->size = 1;
    return(Node);
}
 
// A utility function to right rotate subtree rooted with y
 node *rightRotate(node *y)
{
    node *x = y->left;
    node *T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
 
    // Update sizes
    y->size = size(y->left) + size(y->right) + 1;
    x->size = size(x->left) + size(x->right) + 1;
 
    // Return new root
    return x;
}
 
// A utility function to left rotate subtree rooted with x
 node *leftRotate(node *x)
{
    node *y = x->right;
    node *T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
 
    // Update sizes
    x->size = size(x->left) + size(x->right) + 1;
    y->size = size(y->left) + size(y->right) + 1;
 
    // Return new root
    return y;
}
 
// Get Balance factor of node N
int getBalance(node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
/* Inserts a new key to the tree rotted with node. Also,updates 
*count To contain count of smaller elements for the new key*/
 node* insert( node* node, int key, int *count)
{
    /* 1.  Perform the normal BST rotation */
    if (node == NULL)
        return(newNode(key));
 
    if (key < node->key)
        node->left  = insert(node->left, key, count);
    else
    {
        node->right = insert(node->right, key, count);
 
        // UPDATE COUNT OF SMALLER ELEMENTS FOR KEY
        *count = *count + size(node->left) + 1;
    }
 
 
    /* 2. Update height and size of this ancestor node */
    node->height=max(height(node->left),height(node->right))+1;
    node->size   = size(node->left) + size(node->right) + 1;
 
    /* 3. Get the balance factor of this ancestor node to check 
        whether this node became unbalanced */
    int balance = getBalance(node);
 
    // If this node becomes unbalanced, then there are 4 cases
 
    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    /* return the (unchanged) node pointer */
    return node;
}
 
/* Function to update the countSmaller array to contain count of
    smaller elements on the right side*/
void ConstructSmallerArray(int arr[],int CountSmaller[],int n)
{
  int i, j;
  node *root = NULL;
 
  /* initialize all the counts in countSmaller array as 0*/
  for  (i = 0; i < n; i++)
     CountSmaller[i] = 0;
 
  /* Starting from rightmost element, insert all elements one by
    one in an AVL tree and get the count of smaller elements*/
  for (i = n-1; i >= 0; i--)
  {
     root = insert(root, arr[i], &CountSmaller[i]);
  }
}
 
/*  function that prints out an array on a line */
void printArray(int arr[], int n)
{
  
  for (int i=0; i < n; i++)
    cout<<arr[i]<<" ";
}
 
/* Driver program to test above functions*/
int main()
{
  int arr[] = {4, 7, 12, 9, 10, 2};
  int n = sizeof(arr)/sizeof(arr[0]);
  int low[n];
  cout<<"Input Array: ";
  printArray(arr,n);
  ConstructSmallerArray(arr, low, n);
  cout<<"\nOutput Array: ";
  printArray(low, n);
  return 0;
}

 Output:

Input Array: 4 7 12 9 10 2 
Output Array :1 1 3 1 1 0

Time Complexity:O(NlogN)
Space Complexity:O(N)

Binary Search Tree from preorder traversal

Binary Search Tree from preorder traversal.

Problem statement to create a Binary Search Tree from a preorder traversal

Given only a preorder traversal of a binary search tree (BST), create a tree.

Example:

INPUT:array= {10, 5, 1, 8, 12, 15, 20}
OUTUT:
              10
           /     \
           5      15
         /  \    /  \
         1   8  12   20

Create a Binary Search Tree from a preorder traversal Solution:

Method 1: Brute Force (naive) approach using divide and conquer:-

  1. The first element is always the root.
  2. Then determine the index (i) of first element which is greater than the root.
  3. All elements till ‘i’ are a part of the left subtree.
  4. All elements from ‘i+1′ to ‘n-1′ are a part of the right subtree.
  5. Divide the tree at ‘i’ and recur for both left and right subtrees.

Solution code in C++ for constructing a binary search tree (BST) from a preorder traversal:

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*This function creates a tree from the 
preorder traversal*/
node* buildTree(int arr[], int *rootIndex,
int low, int high, int n)
{
   /*Base Case*/
   if(low > high || *rootIndex >= n)
      return NULL;
      
   /*Create first node as root*/
   node *root = newNode(arr[*rootIndex]);
   *rootIndex = *rootIndex+1;
   
   if (low == high)
      return root;
      
   /*Find first element greater than root*/
   int i;
   for(i=low; i<=high; i++)
   {
      if(arr[i] > root->data)
         break;
   }
   
   root->left = buildTree(arr, rootIndex,  *rootIndex, i-1, n);
   root->right = buildTree(arr, rootIndex, i, high, n);
   
   return root;
}

/*Driver function to test above functions*/
int main() {
   
    int arr[] = {10, 5, 1, 8, 12, 15, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    int rootIndex = 0;
    
    node *root = buildTree(arr, &rootIndex, 0, n-1, n);
   
    cout << "\nInorder traversal of the BST is: ";
    Inorder(root);
   return 0;
}

Output:

Inorder traversal of the BST is: 1 5 8 10 12 15 20

Time Complexity:

Average Case : O(nlogn)
Worst Case : O(n2)


Method 2: Using INT_MIN and INT_MAX:

Set a range for each node to lie between INT_MIN and INT_MAX. The root node always lies within the range. Similarly check for all other nodes while updating the min and max ranges w.r.t. the root for left and right subtree.

Algorithm for creating a Binary Search Tree from preorder traversal:

  1. Initialize INT_MIN and INT_MAX.
  2. The root node lies in this range.
  3. For the left subtree, the range is INT_MIN to root->data.
  4. For the right subtree, range is root->dta to INT_MAX.

Solution code in C++ to build Binary Search Tree from preorder traversal:

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*This function creates a tree from the 
preorder traversal*/
node* buildTree(int arr[], int *rootIndex,int key,
int min, int max, int n)
{
   /*Base Case*/
   if( *rootIndex >= n)
      return NULL;
   
   /*Create a root*/
   node *root = NULL;
   
   /*If the current element lies in range,
   it belongs in the subtree*/
   if (key > min && key < max)
   {
      root = newNode(key);
      *rootIndex = *rootIndex + 1;
      
      if(*rootIndex < n)
      {
         root->left = buildTree(arr, rootIndex, 
         arr[*rootIndex], min, key, n);
         root->right = buildTree(arr, rootIndex, 
         arr[*rootIndex], key, max, n);	
      }
   }
   
   return root;
}

/*Driver function to test above functions*/
int main() {
   
    int arr[] = {10, 5, 1, 8, 12, 15, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    int rootIndex = 0;
    
    node *root = buildTree(arr, &rootIndex, arr[0], INT_MIN, INT_MAX, n);
   
    cout << "\nInorder traversal of the BST is: ";
    Inorder(root);
   return 0;
}

Output:

Inorder traversal of the BST is: 1 5 8 10 12 15 20

Time Complexity: O(n)


Method 3: Using Stacks:

We create an auxiliary stack which stores the data from the given preorder traversal.

Algorithm for creating a Binary Search Tree from preorder traversal:

  1. Create an empty stack.
  2. Initialize the first element as root and push it in the stack.
  3. Traverse from 1 to n-1 and compare each node with the topmost element of the stack.
  4. If it is smaller than the top element, then push it in the stack.
  5. Else pop the stack elements till topmost element of stack is greater than the node.

Solution code in C++ to build Binary Search Tree from preorder traversal:

#include<bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialize new nodes*/
node *newNode(int key)
{
   node *temp = new node;
   temp->left = NULL;
   temp->right = NULL;
   temp->data = key;
   return temp;
}

/*This function is used to print 
Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}


/*This function creates a tree from the 
preorder traversal*/
node *buildTree(int arr[], int n)
{
   /*Create a stack*/
   stack<node*> s;
   
   /*Create first node as root*/
   node *root = newNode(arr[0]);
   
   /*Push the root in stack*/
   s.push(root);
   
   int i;
   node *temp;
   
   /*Traverse through n-1 nodes*/
   for(i=1 ; i<n; i++)
   {
      temp = NULL;
      
      while(!s.empty() && (arr[i]>s.top()->data))
      {
         temp = s.top();
         s.pop();
      }
         
      if(temp != NULL)
      {
         temp->right = newNode(arr[i]);
         s.push(temp->right);
      }
      
      else
      {
         s.top()->left = newNode(arr[i]);
         s.push(s.top()->left);
      }
      
   }
   return root;
}

/*Driver function to test above functions*/
int main(){
   
    int arr[] = {10, 5, 1, 8, 12, 15, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    int rootIndex = 0;
    
    node *root = buildTree(arr, n);
   
    cout << "\nInorder traversal of the BST is: ";
    Inorder(root);
   return 0;
}

 Output:

Inorder traversal of the BST is: 1 5 8 10 12 15 20

Time Complexity: O(n)

Find point of intersection of linked lists

Find intersection point of two Y shaped linked lists – II

NOTE: This post is an extension of Find point of intersection of linked lists.

Problem statement to find intersection point of two linked lists:

Given two singly Y-shaped linked lists, you have to find the intersection point.

Point of intersection of linked lists Example:

Consider two singly Y-shaped linked lists as shown.

Intersection of linked lists

Two intersecting linked lists

The point of intersection of linked lists is given by the node ’30’ which has been highlighted.

Video solution to find point of intersection of linked lists:

Following is a video solution that explains the algorithms that can be used to find the point of intersection of two Y-shaped linked lists.

The codes for the first four algorithms have been given in previous post. Given below are the codes for the remaining three algorithms.

Solutions to find the intersecting point of two Y-shaped linked lists:

Method 5:

The first method for finding the point of intersection of linked lists is by creating equations.

Algorithm to find point of intersection of linked lists:

  1. Traverse first list and count number of nodes, say l1.
  2. Traverse second list and count number of nodes, say l2.
  3. Reverse first list.
  4. Traverse and count uncommon nodes between the two lists starting from head of second list, say l3.
  5. Equations
    1. Let x be nodes in first list from head to intersection point.
      Let y be nodes common nodes between the lists, including intersection point.
      Let z be nodes in second list from head to intersection point.
    2. Thus,
      x+y = l1
      y+z = l2
      x+z = l3
    3. Solving these simultaneous equations:
      x = (l1-l2+l3)/2
      y = (l1+l2-l3)/2
      z = (-l1+l2+l3)/2
    4. Intersection point is the xth node of list 1.
  6. Reverse list 1 again.
  7. Traverse x nodes in list 1 starting from head node. This xth node is the intersection point of linked list.

Solution code in C++ to find point of intersection of linked lists:

NOTE: In this method, we assume that the given two lists are intersecting.

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}
 
/*Function to reverse list iteratively*/
void reverse(node **head)
{
   node *prev, *curr, *next;
   prev = NULL;
   curr = *head;
   while(curr != NULL)
   {
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
   }
   (*head) = prev;
}
 
/*Function to find intersecting point of two linked lists*/
void find_intersection(node *head1,node *head2)
{
   /*initialising node counter of first list as 0*/
   int l1 = 0;
   node *curr1 = head1;
   /*Traversing first list and counting nodes*/
   while(curr1)
   {
      l1++;
      curr1 = curr1->next;
   }
   
   /*initialising node counter of second list as 0*/
   int l2 = 0;
   node *curr2 = head2;
   /*Traversing second list and counting nodes*/
   while(curr2)
   {
      l2++;
      curr2 = curr2->next;
   }

   /*Reversing first list so that uncommon
   nodes between the two lists also form a
   singly linked list*/
   reverse(&head1);
   
   /*initialising node counter for
   counting the uncommon nodes
   between the two lists as 0*/
   int l3 = 0;
   node *curr3 = head2;
   /*Traversing second list and counting nodes*/
   while(curr3)
   {
      l3++;
      curr3 = curr3->next;
   }
   
   /*Setting value of x as ntersectin point*/
   int intersection_pt = (l1-l2+l3)/2;
   
   /*Reversing list1 again to obtain
   original list*/
   reverse(&head1);
   
   /*Traversing first ist till intersection point*/
   for(int i=0 ; i<intersection_pt ; i++)
      head1 = head1->next;
   cout<<"\nIntersection point found: ";
   cout<<head1->data;
}	
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  /*First list*/
  node* head1 = NULL;
  InsFront(&head1, 50);
  InsFront(&head1, 40);
  InsFront(&head1, 30);
  InsFront(&head1, 20);
  InsFront(&head1, 10);
  InsFront(&head1, 1);
 
  /*Second list*/
  node *head2 = NULL;
  InsFront(&head2, 15);
  InsFront(&head2, 5);

  /*Lists converge at node 1*/
  head2->next->next = head1;

  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Calling function to find intersection
  point of two linked lists*/
  find_intersection(head1,head2);
 
  return 0;
}

Output:

Created Linked lists are:
List 1: 1-> 10-> 20-> 30-> 40-> 50-> NULL
List 2: 5-> 15-> 1-> 10-> 20-> 30-> 40-> 50-> NULL
Intersection point found: 1

Time Complexity to find point of intersection of linked lists: O(M+N)
where M and N are the number of nodes of list 1 and list 2 respectively.


Method 6:

The second method for finding the point of intersection of linked lists is by traversing the common number of nodes in both lists and comparing the address of the nodes.

Algorithm to find point of intersection of linked lists:

  1. Count number of nodes in both lists by traversing them. Let these be M and N respectively.
  2. Traverse (M-N) nodes in longer list.
  3. Starting from the next node of longer list and head node of shorter list,compare node addresses.
  4. If a node address matches, that node is the point of intersection.

Solution code in C++ to find point of intersection of linked lists:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}
 
/*Function to find intersecting point of two linked lists*/
void find_intersection(node *head1,node *head2)
{
   node *list1 = head1;
   node *list2 = head2;
   int no_of_nodes_list1 = 0;
   /*Traversing and counting nodes
   in first list*/
   while(list1)
   {
      no_of_nodes_list1++;
      list1 = list1->next;
   }
   
   int no_of_nodes_list2 = 0;  
   /*Traversing and counting nodes
   in second list*/
   while(list2)
   {
      no_of_nodes_list2++;
      list2 = list2->next;
   }
   
   /*Resetting both pointers
   to traverse lists again*/
   list1 = head1;
   list2 = head2;

   /*If list1 is longer*/
   if(no_of_nodes_list1 > no_of_nodes_list2)
   {
      /*Difference between number of nodes of lists*/
      int diff = no_of_nodes_list1 - no_of_nodes_list2;
      
      /*Traversing list1 till a node is
      reached such that after it both
      lists have same number of nodes*/
      for(int i=0 ; i<diff ; i++)
         list1 = list1->next;
   }
   /*If list2 is longer*/
   else if(no_of_nodes_list1 < no_of_nodes_list2)
   {
      /*Difference between number of nodes of lists*/
      int diff = no_of_nodes_list2 - no_of_nodes_list1;
      
      /*Traversing list2 till a node is
      reached such that after it both
      lists have same	number of nodes*/
      for(int i=0 ; i<diff ; i++)
         list2 = list2->next;
   }
   
   /*Traversing both lists for
   equal number of nodes*/
   while(list1 && list2)
   {
      /*If node addresses match*/
      if(list1 == list2)
      {
         cout<<"\nIntersection point found: ";
         cout<<list1->data;
         return;
      }
      list1 = list1->next;
      list2 = list2->next;
   }
   cout<<"\nNo intersection found.";
}	
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  /*First list*/
  node* head1 = NULL;
  InsFront(&head1, 50);
  InsFront(&head1, 40);
  InsFront(&head1, 30);
  InsFront(&head1, 20);
  InsFront(&head1, 10);
  InsFront(&head1, 1);
 
  /*Second list*/
  node *head2 = NULL;
  InsFront(&head2, 15);
  InsFront(&head2, 5);
 
  /*Making lists converge at node 40*/
  head2->next->next = head1->next->next->next-> next ;
  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Calling function to find intersection
  point of two linked lists*/
  find_intersection(head1,head2);
 
  return 0;
}

Output:

Created Linked lists are:
List 1: 1-> 10-> 20-> 30-> 40-> 50-> NULL
List 2: 5-> 15-> 40-> 50-> NULL
Intersection point found: 40

Time Complexity to find point of intersection of linked lists: O(M+N)
where M and N are the number of nodes of list 1 and list 2 respectively.


Method 7:

The third method for detecting a point of intersection of linked lists is by comparing addresses of last nodes.

Algorithm to check if point of intersection of linked lists exists:

  1. Traverse list 1 till last node.
  2. Traverse list 2 till last node.
  3. Compare the addresses of both pointers.
  4. If the addresses are same, an intersecting point exists.

Solution code in C++ to check if point of intersection of linked lists exists:

NOTE: This method is only to check if a point of intersection of linked lists exists.

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}
 
/*Function to find intersecting point of two linked lists*/
void find_intersection(node *head1,node *head2)
{
   /*Traversing first list till last node*/
   while(head1->next)
      head1 = head1->next;

   /*Traversing second list till last node*/
   while(head2->next)
      head2 = head2->next;
   
   /*Comparing addresses of last nodes*/
   if(head1 == head2)
      cout<<"\nIntersection point exists.";
   else
      cout<<"\nNo intersection point exists. ";
}	
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  /*First list*/
  node* head1 = NULL;
  InsFront(&head1, 50);
  InsFront(&head1, 40);
  InsFront(&head1, 30);
  InsFront(&head1, 20);
  InsFront(&head1, 10);
  InsFront(&head1, 1);
 
  /*Second list*/
  node *head2 = NULL;
  InsFront(&head2, 15);
  InsFront(&head2, 5);
 
  /*Lists converge at node 40*/
  head2->next->next = head1->next->next->next->next;
 
  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Calling function to find intersection
  point of two linked lists*/
  find_intersection(head1,head2);
 
  return 0;
}

Output:

Created Linked lists are:
List 1: 1-> 10-> 20-> 30-> 40-> 50-> NULL
List 2: 5-> 15-> 40-> 50-> NULL
Intersection point exists.

Time Complexity to find point of intersection of linked lists: O(M+N)
where M and N are the number of nodes of list 1 and list 2 respectively.

Find point of intersection of linked lists

Find intersection point of two Y shaped linked lists – I

Problem statement to find intersection point of two linked lists:

Given two singly Y-shaped linked lists, you have to find the intersection point.

Point of intersection of linked lists Example:

Consider two singly Y-shaped linked lists as shown.

Intersection of linked lists

Two intersecting linked lists

The point of intersection of linked lists is given by the node ’30’ which has been highlighted.

Video solution to find point of intersection of linked lists:

Following is a video solution that explains the algorithms that can be used to find the point of intersection of two Y-shaped linked lists.

The corresponding codes for the first 4 algorithms have been given below.

Solutions to find the intersecting point of two Y-shaped linked lists:

Method 1:

The first method for finding the point of intersection of linked lists is using iteration.

Algorithm to find point of intersection of linked lists iteratively:

  1. Traverse first list from head node.
  2. Check if any node from second list is same as the node traversed in first list.
  3. The same node is the point of intersection of linked lists.

Solution code in C++ to find point of intersection of linked lists:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}

/*Function to find intersecting point of two linked lists*/
void find_intersection(node *head1,node *head2)
{
   node *curr;
   /*Traversing first list*/
   while(head1)
   {
      /*To start comparisons from head node of
      second list for each node of first list*/
      curr = head2;
      
      /*Traversing second list*/
      while(curr)
      {
         /*Comparing address of current node
         of list 1 with all nodes of list 2*/
         if(head1 == curr)
         {
            cout<<"\n Intersection point found: "<<head1->data;
            return;
         }
         curr = curr->next;
      }
      head1 = head1->next;
   }
   if(head1 == NULL)
      cout<<"\nNo intersection point.";
}
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  /*First list*/
  node* head1 = NULL;
  InsFront(&head1, 50);
  InsFront(&head1, 40);
  InsFront(&head1, 30);
  InsFront(&head1, 20);
  InsFront(&head1, 10);
  InsFront(&head1, 1);
  
  /*Second list*/
  node *head2 = NULL;
  InsFront(&head2, 15);
  InsFront(&head2, 5);
  
  /*Making lists converge at node 30*/
  head2->next->next = head1->next->next->next ;

  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Calling function to find intersection
  point of two linked lists*/
  find_intersection(head1,head2);
  
  return 0;
}

Output:

Created Linked lists are:
List 1: 1-> 10-> 20-> 30-> 40-> 50-> NULL
List 2: 5-> 15-> 30-> 40-> 50-> NULL
 Intersection point found: 30

Time Complexity to find point of intersection of linked lists: O(M.N)
where M and N are the number of nodes of list 1 and list 2 respectively.


Method 2:

The second method for finding the point of intersection of linked lists is by marking visited and unvisited nodes while traversing the list.

Algorithm to find point of intersection of linked lists:

  1. Traverse first list from head node.
  2. Mark all traversed nodes as visited.
  3. Traverse the second list from head node.
  4. Check if any node is marked as visited.
  5. The first visited node is the point of intersection of linked lists.

Solution code in C++ to find point of intersection of linked lists:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
   bool visited;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   temp->visited = false;
   *head = temp; 
}

/*Function to find intersecting point of two linked lists*/
void find_intersection(node *head1,node *head2)
{
   /*Traversing first list*/
   while(head1)
   {
      /*Marking traversed node as visited*/
      head1->visited = true;
      head1 = head1->next;
   }
   
   /*Traversing second list*/
   while(head2)
   {
      /*Checking if any traversed node
      has already been visited*/
      if(head2->visited == true)
      {
         cout<<"\nIntersecting point found: ";
         cout<<head2->data;
         return;
      }
      head2 = head2->next;
   }
   cout<<"\nNo intersection found.";
}	
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  /*First list*/
  node* head1 = NULL;
  InsFront(&head1, 50);
  InsFront(&head1, 40);
  InsFront(&head1, 30);
  InsFront(&head1, 20);
  InsFront(&head1, 10);
  InsFront(&head1, 1);
  
  /*Second list*/
  node *head2 = NULL;
  InsFront(&head2, 15);
  InsFront(&head2, 5);
  
  /*Making lists converge at node 30*/
  head2->next->next = head1->next->next->next ;
  
  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Calling function to find intersection
  point of two linked lists*/
  find_intersection(head1,head2);
  
  return 0;
}

Output:

Created Linked lists are:
List 1: 1-> 10-> 20-> 30-> 40-> 50-> NULL
List 2: 5-> 15-> 30-> 40-> 50-> NULL
Intersecting point found: 30

Time Complexity to find point of intersection of linked lists: O(M+N)
where M and N are the number of nodes of list 1 and list 2 respectively.


Method 3:

The third method for finding the point of intersection of linked lists is by using hashing.

Algorithm to find point of intersection of linked lists using hash map:

  1. Traverse and insert all nodes of first list into a Hash map.
  2. Check if a node from the second list exists in the hash map.
  3. The first node found to be in hash map is the point of intersection of linked lists.

Solution code in C++ to find point of intersection of linked lists:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
   bool visited;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   temp->visited = false;
   *head = temp; 
}
 
/*Function to find intersecting point of two linked lists*/
void find_intersection(node *head1,node *head2)
{
   /*Defining hash table with node pointer
   as key and bool type as value which will
   be true or false depending on whether a 
   node is in hash map or not*/
   map <node*,bool> visited;
   
   /*Traversing first list*/
   while(head1)
   {
      /*Hashing each node*/
      visited[head1] = true;
      head1 = head1->next;
   }
   
   /*Traversing second list*/
   while(head2)
   {
      /*Creating iterator for hash map*/
      map <node*,bool>::iterator i;
      
      /*Find function will search the hash map
      for "head2" and return an iterator to it
      if it is found else it will return an
      iterator to past-the-last element in map*/
      i = visited.find(head2);
      
      /*If "head2" is found in map*/
      if(i != visited.end())
         {
            cout<<"\nIntersection point found: ";
            cout<<head2->data;
            return;
         }
      head2 = head2->next;
   }
   cout<<"\nNo intersection point found.";
}	
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  /*First list*/
  node* head1 = NULL;
  InsFront(&head1, 50);
  InsFront(&head1, 40);
  InsFront(&head1, 30);
  InsFront(&head1, 20);
  InsFront(&head1, 10);
  InsFront(&head1, 1);
 
  /*Second list*/
  node *head2 = NULL;
  InsFront(&head2, 50);
  InsFront(&head2, 40);
  InsFront(&head2, 30);  
  InsFront(&head2, 15);
  InsFront(&head2, 5);
  /*NO CONVERGING POINT SET BETWEEN THE LINKED LISTS*/
  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Calling function to find intersection
  point of two linked lists*/
  find_intersection(head1,head2);
 
  return 0;
}

Output:

Created Linked lists are:
List 1: 1-> 10-> 20-> 30-> 40-> 50-> NULL
List 2: 5-> 15-> 30-> 40-> 50-> NULL
No intersection point found.

Time Complexity to find point of intersection of linked lists: O(M+N)
where M and N are the number of nodes of list 1 and list 2 respectively.


Method 4:

The fourth method for finding the point of intersection of linked lists is by creating a loop in the first linked list.

Algorithm to find point of intersection of linked lists by creating a loop:

  1. Traverse the first list starting from head node and count the number of nodes, say N.
  2. Set the next of last node as the head node i.e. create a loop in first linked list.
  3. Traverse second list using a pointer, say “ptr1″, from its head node for N nodes.
  4. Traverse second list again from first node using another pointer, say “ptr2″.
  5. Increment “ptr1″ and “ptr2″ to corresponding next nodes, simultaneously.
  6. When ptr1=ptr2, the point of intersection of linked lists is obtained.

Solution code in C++ to find point of intersection of linked lists:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
   bool visited;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   temp->visited = false;
   *head = temp; 
}
 
/*Function to find intersecting point of two linked lists*/
void find_intersection(node *head1,node *head2)
{
   node *curr1 = head1;

   /*initialising node counter as 1 as
   the loop will not run for last node*/
   int no_of_nodes1 = 1;

   /*Traversing first list and counting nodes*/
   while(curr1->next)
   {
      no_of_nodes1++;
      curr1 = curr1->next;
   }
   
    /*Creating loop in first list*/
   	curr1->next = head1;
   
    /*Traversing a number of nodes in
    second list which is equal to the
    number of nodes in the first list*/
    node *curr2 = head2;
    for(int i=0 ; i<no_of_nodes1 ; i++)
    {
    	/*If lists are not intersecting
    	and list2 is shorter than list1
    	curr2 will reach NULL*/
    	if(!curr2)
    	{
    	    cout<<"\nNo intersection point found.";
    	    return;
    	}
    	curr2 = curr2->next;
    }
   
   /*Traversing the second list
   from the head node using head
   pointer till head pointer and
   curr2 reach the same node*/
   while(head2 && curr2)
   {
      head2 = head2->next;
      curr2 = curr2->next;
      if(head2 == curr2)
      {
         cout<<"\nIntersection point found: ";
         cout<<curr2->data;
         return;
      }
   }
}	
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  /*First list*/
  node* head1 = NULL;
  InsFront(&head1, 50);
  InsFront(&head1, 40);
  InsFront(&head1, 30);
  InsFront(&head1, 20);
  InsFront(&head1, 10);
  InsFront(&head1, 1);
 
  /*Second list*/
  node *head2 = NULL;
  InsFront(&head2, 15);
  InsFront(&head2, 5);

  /*Lists converge at node 10*/
  head2->next->next = head1->next;

  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Calling function to find intersection
  point of two linked lists*/
  find_intersection(head1,head2);
 
  return 0;
}

Output:

Created Linked lists are:
List 1: 1-> 10-> 20-> 30-> 40-> 50-> NULL
List 2: 5-> 15-> 10-> 20-> 30-> 40-> 50-> NULL
Intersection point found: 10

Time Complexity to find point of intersection of linked lists: O(M+N)
where M and N are the number of nodes of list 1 and list 2 respectively.

Intersection of two sorted linked lists

Intersection of lists which are sorted

Problem statement to find intersection of linked lists:

Given two sorted singly linked lists, you have to form a new linked list containing the nodes common to both lists i.e. the new linked list is the intersection of the two given linked lists.

Intersection of lists Example:

Consider two sorted singly linked lists
 List 1: 10-> 20-> 24-> 28-> 30-> 36-> 40-> NULL
 List 2: 5-> 10-> 18-> 24-> 35-> 36-> 38-> 40-> NULL
Intersection of lists will be
 10-> 24-> 36-> 40-> NULL

Solution to find intersection of lists:

Method 1 (Iteratively):

Algorithm to find intersection of linked lists:

  1. Traverse both lists starting from corresponding head nodes.
  2. Compare the nodes of both lists.
    1. If nodes are equal, add the node at end of new list.
      1. Move pointers of both lists to corresponding next nodes.
    2. If node of list1 is smaller in value, move pointer of list1 to next node.
    3. If node of list2 is smaller in value, move pointer of list2 to next node.

Solution code in C++ to find intersection of lists:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes at end of Linked List*/
void InsEnd(node **head, node **last, int data)
{
    node *temp = new node;
    temp->data = data;
    temp->next = NULL;
 
    /*If list is empty.*/
    if(*head == NULL)
    {
        /*The first node is the head and last node*/
        *head = temp; 
        *last = temp;
    }
 
    else
    {
    	(*last)->next = temp;
    	*last = temp;
    }
}
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/*Function to find intersection of two linked lists*/
void intersection(node *head1,node *head2)
{
   node *curr1 = head1;
   node *curr2 = head2;
   
   /*Initialising new list*/
   node *head3 = NULL;
   node *last3 = NULL;
   
   /*Traversing both lists*/
   while(curr1 && curr2)
   {
      /*If data is equal*/
      if(curr1->data == curr2->data)
      {
         /*Insert node at end of new list*/
         InsEnd(&head3,&last3,curr1->data);
         /*Moving both pointers to next nodes*/
         curr1 = curr1->next;
         curr2 = curr2->next;
      }
      
      else if(curr1->data < curr2->data)
         curr1 = curr1->next;
      
      else if(curr1->data > curr2->data)
         curr2 = curr2->next;
   }
   cout<<"\nIntersection of lists: ";
   printList(head3);
}	
 
/* Driver program to test above functions*/
int main()
{	
  /*First list*/
  node* head1 = NULL;
  node* last1 = NULL;
  InsEnd(&head1, &last1, 10);
  InsEnd(&head1, &last1, 20);
  InsEnd(&head1, &last1, 24);
  InsEnd(&head1, &last1, 28);
  InsEnd(&head1, &last1, 30);
  InsEnd(&head1, &last1, 36);
  InsEnd(&head1, &last1, 40); 

  /*Second list*/
  node* head2 = NULL;
  node* last2 = NULL;
  InsEnd(&head2, &last2, 5);
  InsEnd(&head2, &last2, 10);
  InsEnd(&head2, &last2, 18);
  InsEnd(&head2, &last2, 24);
  InsEnd(&head2, &last2, 35);
  InsEnd(&head2, &last2, 36);
  InsEnd(&head2, &last2, 38);
  InsEnd(&head2, &last2, 40);

  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Calling function to find
  intersection of linked lists*/
  intersection(head1,head2);
 
  return 0;
}

Output:

Created Linked lists are:
List 1: 10-> 20-> 24-> 28-> 30-> 36-> 40-> NULL
List 2: 5-> 10-> 18-> 24-> 35-> 36-> 38-> 40-> NULL
Intersection of lists: 10-> 24-> 36-> 40-> NULL

Time Complexity to find intersection of linked lists: O(M+N)
where M and N are number of nodes in List1 and List2 respectively.


Method 2 (Recursively):

Algorithm to find intersection of linked lists using recursion:

  1. Call recursive function to find intersection of lists with head pointers as arguements.
  2. Compare the current nodes of both lists.
    1. If nodes are equal.
      1. Create a new node.
      2. Set data of new node as data of node in list1 or list2.
      3. Recursively call function by passing next nodes of both lists as parameters.
      4. Store return value in ‘next’ of new node.
    2. If node of list1 is smaller in value, recursively call function by passing list1->next and list2 as parameters.
    3. If node of list2 is smaller in value, recursively call function by passing list1 and list2->next as parameters.
  3. If either of the current nodes are NULL, return NULL.

Solution code in C++ to find intersection of lists:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes at end of Linked List*/
void InsEnd(node **head, node **last, int data)
{
    node *temp = new node;
    temp->data = data;
    temp->next = NULL;
 
    /*If list is empty.*/
    if(*head == NULL)
    {
        /*The first node is the head and last node*/
        *head = temp; 
        *last = temp;
    }
 
    else
    {
    	(*last)->next = temp;
    	*last = temp;
    }
}
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/*Function to find intersection of two linked lists*/
node* intersection(node *list1,node *list2)
{
   /*If either of current nodes of lists is NULL*/
   if(list1 == NULL || list2 == NULL)
      return NULL;
   
   if(list1->data < list2->data)
      /*Recursive function call for next node
      of list1 and current node of list2.*/
      return intersection(list1->next,list2);
   
   if(list2->data < list1->data)
      /*Recursive function call for next node
      of list2 and current node of list1.*/
      return intersection(list1,list2->next);
      
   if(list1->data == list2->data)
   {	
      node *list3 = new node;
      list3->data = list1->data;
      /*Recursive function call for next nodes of both lists.*/
      list3->next = intersection(list1->next,list2->next);
      return list3;
   }
}
 
/* Driver program to test above functions*/
int main()
{	
  /*First list*/
  node* head1 = NULL;
  node* last1 = NULL;
  InsEnd(&head1, &last1, 10);
  InsEnd(&head1, &last1, 20);
  InsEnd(&head1, &last1, 24);
  InsEnd(&head1, &last1, 28);
  InsEnd(&head1, &last1, 30);
  InsEnd(&head1, &last1, 36);
  InsEnd(&head1, &last1, 40); 

  /*Second list*/
  node* head2 = NULL;
  node* last2 = NULL;
  InsEnd(&head2, &last2, 5);
  InsEnd(&head2, &last2, 10);
  InsEnd(&head2, &last2, 18);
  InsEnd(&head2, &last2, 24);
  InsEnd(&head2, &last2, 35);
  InsEnd(&head2, &last2, 36);
  InsEnd(&head2, &last2, 38);
  InsEnd(&head2, &last2, 40);

  cout<<"Created Linked lists are:";
  cout<<"\nList 1: ";
  printList(head1);
  cout<<"\nList 2: ";
  printList(head2);
 
  /*Initialising new list*/
   node *head3 = NULL;
   
  /*Calling function to find
  intersection of linked lists*/
  head3 = intersection(head1,head2);
  
  cout<<"\nIntersection List: ";
  printList(head3);
 
  return 0;
}

Output:

Created Linked lists are:
List 1: 10-> 20-> 24-> 28-> 30-> 36-> 40-> NULL
List 2: 5-> 10-> 18-> 24-> 35-> 36-> 38-> 40-> NULL
Intersection List: 10-> 24-> 36-> 40-> NULL

Time Complexity to find intersection of linked lists: O(M+N)
where M and N are number of nodes in List1 and List2 respectively.

Rotate Linked List

Rotating a Linked List Anti-clockwise

Problem statement for Linked List Rotation:

Given a singly linked list, you have to rotate linked list by ‘x’ nodes, anti-clockwise.

Rotate linked list Example:

Consider a singly linked list
 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> NULL
Rotating linked list anti-clockwise by 6 nodes
 7-> 8->1-> 2-> 3-> 4-> 5-> 6-> NULL

Algorithm to Rotate linked list anti-clockwise by x nodes:

  1. Traverse the linked list till xth node.
  2. Store address of xth node in a pointer.
  3. Traverse list till last node.
  4. Set next of last node as head node.
  5. Set head as (x+1)th node.
  6. Set xth node as last node i.e. next points to NULL.

Solution code in C++ to rotate linked list anti-clockwise:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}
 
/*Function to rotate list by x nodes*/
void Rotate(node **head,int x)
{
   node *curr = *head;
   
   /*Traversing list so that 
   curr points to xth node*/
   for(int i=1 ; i<x ; i++)
      curr = curr->next;
   
   /*Storing xth node*/
   node *xth_node = curr;
   
   /*Traversing list till last node*/
   while(curr->next)
      curr = curr->next;
   
   /*Setting next of (x+1)th node as head*/
   curr->next = (*head);
   
   /*Setting (x+1)th node as head*/
   (*head) = xth_node->next;

   /*Setting xth node as last node*/
   xth_node->next = NULL;
}
 
/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
/* Driver program to test above functions*/
int main()
{
  node* head = NULL;
  InsFront(&head, 8);
  InsFront(&head, 7);
  InsFront(&head, 6); 
  InsFront(&head, 5);
  InsFront(&head, 4);
  InsFront(&head, 3);
  InsFront(&head, 2);
  InsFront(&head, 1);
 
  cout<<"Created Linked list is:\n";
  printList(head);
 
  /*Calling function to rotate list by 6 nodes*/
  Rotate(&head,6);
  cout<<"\nResultant Linked list is:\n";
  printList(head);
  
  return 0;
}

 Output:

Created Linked list is:
1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> NULL
Resultant Linked list is:
7-> 8-> 1-> 2-> 3-> 4-> 5-> 6-> NULL

Time Complexity to rotate linked list by x nodes : O(N) 
whee N is the number of nodes in the linked list.

Merge Sort a Linked List

Merge Sort a Linked list

Problem statement to merge sort list:

Given a singly linked list, you have to sort the linked list using merge sort.

Merge sort list Example:

Consider a linked list
8-> 3-> 2-> 9-> 7-> 1-> 5-> 4-> NULL
After merge sort, the resultant list should be
1-> 2-> 3-> 4-> 5-> 7-> 8-> 9-> NULL

Video solution to merge sort list:

Algorithm to merge sort list:

  1. If list is empty or has only one element, return.
  2. Else, split the linked list into two halves by finding middle node.
  3. Sort the two halves.
  4. Combine the sorted halves.

Solution code in C++ to merge sort list:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}

/*Function to split list into two halves. 'half1'
and 'half2' point to first nodes of two halves*/
void Split(node *head, node **half1,node **half2)
{
   node *ptr1 = head;
   node *ptr2 = head->next;
   
   /*If list is empty or has only 1 node*/
   if(head == NULL || head->next == NULL)
   {
      (*half1) = head;
      (*half2) = NULL;
   }
   
   else
   {
      /*When loop ends, ptr1 reaches middle node*/
      while(ptr2 && ptr2->next)
      {
         ptr1 = ptr1->next;
         ptr2 = ptr2->next->next;
      }
      
      /*half1 points to first node of first half*/
      *half1 = head;
      /*half2 points to first node of second half*/
      *half2 = ptr1->next;
      /*Seperates two halves of list*/
      ptr1->next = NULL;
   }
}

/*Function to merge the sorted halves*/
node* merge(node *half1, node *half2)
{
   if(half1 == NULL)
      return half2;
   if(half2 == NULL)
      return half1;
   
   /*Initialising pointer to merged list*/
   node *merged_list;
  
   /*Comparing node values*/
   if(half1->data <= half2->data)
   {
      /*Inserting smaller node in merged lsit*/
      merged_list = half1;
      /*Recursive function call to compare next nodes*/
      merged_list->next = merge(half1->next,half2);
   }
   
   else if(half1->data > half2->data)
   {
      /*Inserting smaller node in merged lsit*/
      merged_list = half2;
      /*Recursive function call to compare next nodes*/
      merged_list->next = merge(half1,half2->next);
   }
 
   /*Returning pointer to first node of merged list*/
   return merged_list;
}

/*Function to apply merge sort*/
void merge_sort(node **head)
{
   /*Empty list or only a single node*/
   if((*head) == NULL || (*head)->next == NULL)
      return;

   /*Declaring pointers to two halves of list*/   
   node *half1 , *half2;

   /*Calling function to split the list into two halves*/
   Split(*head,&half1,&half2);
   
   /*Calling function recursively to sort first half*/
   merge_sort(&half1);

   /*Calling function recursively to sort second half*/
   merge_sort(&half2);
   
   /*Calling function to merge the sorted halves.
   'head' points to first node of merged lists*/
   *head = merge(half1,half2);
}

/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}

/* Driver program to test above functions*/
int main()
{
  node* head = NULL;
  InsFront(&head, 4);
  InsFront(&head, 5);
  InsFront(&head, 1);
  InsFront(&head, 7);
  InsFront(&head, 9);
  InsFront(&head, 2);
  InsFront(&head, 3);
  InsFront(&head, 8);
  
  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Calling merge sort function*/
  merge_sort(&head);
  cout<<"\nResultant Linked list is:\n";
  printList(head);
   
  return 0;
}

 Output:

Created Linked list is:
8-> 3-> 2-> 9-> 7-> 1-> 5-> 4-> NULL
Resultant Linked list is:
1-> 2-> 3-> 4-> 5-> 7-> 8-> 9-> NULL

Time Complexity to merge sort list: O(NlogN)
where N is the number of nodes in the list.