Monthly Archives: March 2016

Sort linked list whose alternate nodes are in ascending and descending order

Sort list whose alternate nodes are in ascending and descending order without using sorting techniques

Problem statement to sort list whose alternate nodes are in ascending and descending order:

Given is a singly linked list whose alternate nodes are sorted in ascending and descending order i.e. nodes at odd positions form an ascending ordered linked list and nodes at even positions form a descending ordered linked list. You have to sort this entire list in ascending order without using any sorting technique.

Sort list whose alternate nodes are in ascending and descending order Example:

Consider a singly linked list whose alternate nodes are 
in ascending and descending order
1-> 45-> 8 -> 23-> 19-> 11-> 34-> 5-> 67-> NULL
Resultant list after sorting
1-> 5-> 8-> 11-> 19-> 23-> 34-> 45-> 67-> NULL

Algorithm to sort list whose alternate nodes are in ascending and descending order without using any sorting technique:

  1. Seperate the list into two lists which are in ascending and descending order respectively.
  2. Reverse the list which is in descending order.
  3. Merge this list with the ascending ordered list.

Solution code in C++ to sort list whose alternate nodes are in ascending and descending order without using any sorting technique:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function inserts nodes at end of Linked List*/
void Insert(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 reverses list*/
void Reverse(node **head)
{
   node *prev = NULL;
   node *curr = *head;
   node *next = NULL;
   while(curr)
   {
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
   }
   *head = prev;
}

/*Function applies sorted merge on the lists
and returns head pointer of sorted list.*/
node* Merge(node *desc_list, node *asc_list)
{
   /*Pointers to final sorted list*/
   node *sorted_list = NULL;
   node *last = NULL;
   
   /*Loop to traverse both lists simultaneously
   and insert smaller node into sorted list*/
   while(desc_list != NULL && asc_list != NULL)
   {
      if(asc_list->data < desc_list->data)
      {
         Insert(&sorted_list,&last,asc_list->data);
         asc_list = asc_list->next;
      }
      
      else if(desc_list->data < asc_list->data)
      {
         Insert(&sorted_list,&last,desc_list->data);
         desc_list = desc_list->next;
      }
      
      else
      {
         Insert(&sorted_list,&last,asc_list->data);
         Insert(&sorted_list,&last,desc_list->data);	
         asc_list = asc_list->next;
         desc_list = desc_list->next;
      }
   }
   
   /*If number of nodes in asc_list
   are less than that in desc_list*/
   while(desc_list != NULL)
   {
      Insert(&sorted_list,&last,desc_list->data);
      desc_list = desc_list->next;
   }
   
   /*If number of nodes in desc_list
   are less than that in asc_list*/
   while(asc_list != NULL)
   {
      Insert(&sorted_list,&last,asc_list->data);
      asc_list = asc_list->next;
   }
   
   /*Returns head pointer of sorted list*/
   return sorted_list;
}

/*Function to sort linked
list in ascending order*/
void Sort(node **head)
{
   /*Initialising pointers
   of ascending list*/
   node *asc_head = NULL;
   node *asc_tail = NULL;

   /*Initialising pointers
   of descending list*/
   node *desc_head = NULL;
   node *desc_tail = NULL;

   node *curr = *head;
   int i = 1;

   /*Loop traverses and splits given list*/
   while(curr != NULL)
   {
      /*Nodes at odd positions inserted in asc_list*/
      if(i % 2 != 0)
         Insert(&asc_head, &asc_tail, curr->data);
      
      /*Nodes at even positions inserted in desc_list*/
      else
         Insert(&desc_head, &desc_tail, curr->data);
      
      i++;
      curr = curr->next;
   }
   
   /*Call function to reverse desc_list*/
   Reverse(&desc_head);
   
   /*Call function to merge the two lists*/
   *head = Merge(desc_head, asc_head);
}

/*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()
{
    /*initialising head and 
    last pointers to list*/
    node* head = NULL;
    node* last = NULL;
 
    /*Inserts nodes at end of list*/
    Insert(&head, &last, 1);
    Insert(&head, &last, 45);
    Insert(&head, &last, 8);
    Insert(&head, &last, 23);
    Insert(&head, &last, 19); 
    Insert(&head, &last, 11);
    Insert(&head, &last, 34);
    Insert(&head, &last, 1); 
    Insert(&head, &last, 67);

    cout<<"Created Linked list is:\n";
    printList(head);
  
    /*Calling sort function*/
    Sort(&head);

    cout<<"\nResultant Linked list is:\n";
    printList(head);
  
    return 0;
}

Output:

Created Linked list is:
1-> 45-> 8-> 23-> 19-> 11-> 34-> 1-> 67-> NULL
Resultant Linked list is:
1-> 1-> 8-> 11-> 19-> 23-> 34-> 45-> 67-> NULL

Time complexity to perform this sort list without using any sorting technique: O(N)
where N is the number of nodes in the given linked list.

Find Pythagorean Triplet in an Array

Find Pythagorean Triplet in an Array

In this post we deal with the problem of finding a pythagorean triplet in the given array.

How to Find Pythagorean Triplet in an Array Problem Statement:

Given an array of n integers , we need to write a function that returns true if any  elements of the array satisfy the pythagoras theorem
i.e. a^2 + b^2 = c^2. We can solve the problem using two approaches as discussed below.

Finding Pythagorean Triplet in an Array Example:

Input array : arr[] = { 1, 8, 2, 10, 6, 9 }
 Output : true // Triplet (8, 9, 10)
Input array : arr[] = { 2, 8, 1, 6, 15 }
 Output : false //No triplet

Pythagorean Triplet in an Array Solution:

Method 1:

In this method we use a brute force approach and check all possible pairs. We run three loops,three loops pick three array elements and check if current three elements form a Pythagorean Triplet.

Algorithm:

  1. Run three loops
  2. Check if the picked three elements form a pythagorean triplet.

Finding pythagorean triplet solution code in C++:

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

// Returns true if there is Pythagorean triplet in ar[0..n-1]
bool isTriplet(int arr[], int n)
{
    for (int i=0; i<n; i++)
    {
       for (int j=i+1; j<n; j++)
       {
          for (int k=j+1; k<n; k++)
          {
            // Calculate square of array elements
            int x = arr[i]*arr[i],y = arr[j]*arr[j]
            int z = arr[k]*arr[k];
 
            if (x == y + z || y == x + z || z == x + y)
            {
               cout<<"Triplet Found :"<<arr[i]<<" "<<arr[j];
               cout<<" "<<arr[k];
               return true;
            }
          }
       }
    }
 
    // If we reach here, no triplet found
    cout<<"No triplet found ";
    return false;
}
 
/* Driver program to test above function */
int main()
{
    int arr[] = {3, 1, 4, 6, 5};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    isTriplet(arr, arr_size);
    return 0;
}

 Output :

Triplet Found :3 4 5

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


Method 2:

In this method we first square each element of the array. We now sort the array in incresing order. All we need to do is find a triplet (a,b,c) such that a = b + c. We do so by fixing ‘a’ as last element of the array and finding (b,c).

Algorithm:

  1. Square each element of the array.
  2. Sort the array in increasing order.
  3. To find a triplet (a, b, c) such that a = b + c, do following.
    1. Fix ‘a’ as last element of sorted array.
    2. Now search for pair (b, c) in subarray between first element and ‘a’.
    3. If no pair found for current ‘a’, then move ‘a’ one position back and repeat step 3.b.

Finding pythagorean triplet solution code in C++:

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

/* Returns true if there is a triplet with following property
    A[i]*A[i] = A[j]*A[j] + A[k]*[k]*/
bool isTriplet(int arr[], int n)
{
    // Square array elements
    for (int i=0; i<n; i++)
        arr[i] = arr[i]*arr[i];
 
    // Sort array elements
    sort(arr, arr + n);
 
    /*Now fix one element one by one and find the other two
         elements*/
    for (int i = n-1; i >= 2; i--)
    {
        /* To find the other two elements, start two index
            variables from two corners of the array and move
            them toward each other  */
        int l = 0; // index of the first element in arr[0..i-1]
        int r = i-1; // index of the last element in arr[0..i-1]
        while (l < r)
        {
            // A triplet found
            if (arr[l] + arr[r] == arr[i])
            {
               cout<<"Triplet Found ";
                return true;
            }
 
            // Else either move 'l' or 'r'
            (arr[l] + arr[r] < arr[i])?  l++: r--;
        }
    }
 
    // If we reach here, then no triplet found
    cout<<"No Triplet Found ";
    return false;
}
 
/* Driver program to test above function */
int main()
{
    int arr[] = {3, 1, 4, 6, 5};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    isTriplet(arr, arr_size);
    return 0;
}

Output : 

Triplet Found

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

Note : This method modifies the original array.

Insertion sort on a singly linked list

Insertion sort list

Problem statement for insertion sort list (linked list):

Given a singly linked list, you have to apply insertion sort on linked list.

Insertion sort list Example:

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

Insertion sort list Algorithm:

For insertion sort on linked lists, swapping is NOT feasible as is done when insertion sort is applied on arrays. Hence, a different method is used for insertion sort list.

  1. Traverse a node in unsorted list.
  2. Insert this node in a resultant list in sorted manner.
  3. Repeat till entire list is traversed.

Solution code in C++ for insertion 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 that inserts nodes in sorted order*/
void sorted_insert(node **head, int n)
{
   /*New node allocation and 
   data storage common to all
   parts of this function*/
   node *temp = new node;
   temp->data = n;
 
   /*If list is empty or n is the smallest*/
   if(*head == NULL||(*head)->data >= n)
   {
      /*n is set as the first node in list*/
      temp->next = *head;
      *head = temp;
   }
 
   else
   {
      /*pointers to first and second node*/
      node *prev = *head;
      node *curr = prev->next;
 
      /*Loop runs till entire list is traversed*/
      while(curr != NULL)
      {
         /*If value of 'n' is between value of prev and curr*/
         if(prev->data < n && n < curr->data)
         {
            /*Insert 'n' between prev and curr*/
            prev->next = temp;
            temp->next = curr;
            return;
         }
 
         /*Move prev and curr to next positions*/
         prev = prev->next;
         curr = curr->next;
      }
 
      /*If curr=NULL, n is entered at end of list*/
      prev->next = temp;
      temp->next= curr;
   }
}

/*Function to apply insertion sort on list*/
void ins_sort(node **head)
{
   /*Base case*/
   if(*head == NULL)
      return;
   
   /*Creating an empty sorted list*/
   node *sorted_list = NULL;
   
   node *curr = *head;
   
   /*Traversing entire list*/
   while(curr != NULL)
   {
      /*Insert each node in sorted manner in
      new linked list using 'Sorted Insert'*/
      sorted_insert(&sorted_list,curr->data);
      curr = curr->next;
   }
   
   /*Updating head of unsorted list to
   point to first node of sorted list*/
   *head = sorted_list;
}

/*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;
 
   /*Creating unsorted list*/
    InsFront(&head, 6);
    InsFront(&head, 5);
    InsFront(&head, 9);
    InsFront(&head, 9);
    InsFront(&head, 1);
    InsFront(&head, 8);
    InsFront(&head, 2);
    InsFront(&head, 7);
    InsFront(&head, 3);
  
    cout<<"Created Linked list is:\n";
    printList(head);
 
    /*Calling Insertion sort function*/
    ins_sort(&head);
    
    cout<<"\nResultant Linked list is:\n";
    printList(head);
    
  return 0;
}

 Output:

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

Time Complexity for insertion sort on linked list: O(N)
where N is the number of nodes in the linked list.

Sorted insert in linked list

Sorted insert in linked list

Problem statement for sorted insert in linked list:

Given a sorted singly linked list, you have to insert nodes into the linked list in sorted order.

Sorted insert in linked list Example:

Consider a sorted singly linked list
1-> 2-> 6-> 19-> 28-> NULL
After inserting, say 10, resultant linked list will be
1-> 2-> 6-> 10-> 19-> 28-> NULL

Video explanation for sorted insert in linked list:

Sorted insert in linked list Algorithm:

Here is an algorithm for sorted insert, of a node say M, in a linked list.

  1. If the linked list is empty, make M the head node of the list.
  2. If the list is non- empty-
    1. If M < head->data, insert M at the front of list.
    2. If M > head->data and M < last_node->data, insert M in order in list.
    3. Else, insert M at end of linked list.

Solution code in C++ for sorted insert in linked 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 sorted order*/
void sorted_insert(node **head, int n)
{
   /*New node allocation and 
   data storage common to all
   parts of this function*/
   node *temp = new node;
   temp->data = n;
   
   /*If list is empty or n is the smallest*/
   if(*head == NULL||(*head)->data >= n)
   {
      /*n is set as the first node in list*/
      temp->next = *head;
      *head = temp;
   }
      
   else
   {
      /*pointers to first and second node*/
      node *prev = *head;
      node *curr = prev->next;
      
      /*Loop runs till entire list is traversed*/
      while(curr != NULL)
      {
         /*If value of 'n' is between value of prev and curr*/
         if(prev->data < n && n < curr->data)
         {
            /*Insert 'n' between prev and curr*/
            prev->next = temp;
            temp->next = curr;
            return;
         }
      
         /*Move prev and curr to next positions*/
         prev = prev->next;
         curr = curr->next;
      }
      
      /*If curr=NULL, n is entered at end of list*/
      prev->next = temp;
      temp->next= curr;
   }
}

/*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;

    /*Calling function to insert in sorted order*/
    sorted_insert(&head, 6);
    sorted_insert(&head, 28);
    sorted_insert(&head, 2);
    sorted_insert(&head, 19);
    sorted_insert(&head, 1);
    sorted_insert(&head, 10);
  
    cout<<"Created Linked list is:\n";
    printList(head);
  
  return 0;
}

 Output:

Created Linked list is:
1-> 2-> 6-> 10-> 19-> 28-> NULL

Time Complexity for sorted insert in linked list: O(N)
where N is the number of nodes in the linked list.

Quicksort a linked list

Quicksort a linked list

Problem statement to quicksort list:

Given a singly linked list, you have to apply quicksort on the linked list.

Quicksort list Example:

Consider a singly linked list
23-> 3-> 1-> 9-> 10-> 8-> NULL
Resultant list should be
1-> 3-> 8-> 9-> 10-> 23-> NULL

Algorithm to quicksort list:

  1. Partition
    1. Select last node as pivot.
    2. Compare all nodes with pivot.
      1. A node smaller than pivot is left unchanged.
      2. A node greater than pivot is placed on the right side of pivot.
      3. The new position of pivot, say ‘mid’, is returned.
  2.  Quicksort
    1. Find partition.
    2. Call quicksort recursively for sub-list before the partition node.
    3. Call quicksort recursively for sub-list after the partition node.
    4. Combine sorted parts.

Solution code in C++ to quicksort 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 returns last node of list*/
node* last_node(node *head)
{
   while(head->next != NULL)
      head = head->next;
   return head;
}

/*Functions returns pivot's correct position in list*/
node* partition(node **head, node **last)
{
   /*Variable to check if new
   head has been allocated*/
   int is_head_new = 0;

   /*Last node is chosen as pivot*/
   node *pivot = *last;

   node *prev = NULL;
   node *curr = *head;

   /*Loop runs till all nodes greater 
   than the pivot are placed on its right
   and all lesser than it placed on left*/
   while(curr != pivot)
   {
      if(curr->data <= pivot->data)
      {
         /*If no new head has been allocated*/
         if(is_head_new == 0)
         {
            /*Allocates new head as the
            first smallest node in list*/
            (*head) = curr; 
            
            /*Indicates new head has been allocated*/
            is_head_new = 1;
         }
         
         /*Pointers are moved to corresponding 
         next nodes to compare with pivot*/
         prev = curr;
         curr = curr->next;
      }
      
      else if(curr->data > pivot->data)
      {
         /*If a node other than first
         node is greater than pivot*/
         if(prev != NULL)
            prev->next = curr->next;
      
         /*'curr' node is shifted
         to the end of the list*/
         node *temp = curr->next;
         curr->next = NULL;
         (*last)->next = curr;
         (*last) = curr;
      
         /*'curr' is moved to next node*/
         curr = temp;
      }
   }
   
   /*pivot is the smallest node*/
   if(is_head_new == 0)
   {
      /*correct position of pivot will
      be at the front of the list*/
      (*head) = pivot;
   }

   return pivot;
}

/*Function to apply quicksort on list*/
node* quick_sort(node *head, node *last)
{
   /*List has more than 1 element*/
   if(head != NULL && head != last )
   {
      /*'mid' points to pivot in its correct
      position in the list using partition function*/
      node *mid = partition(&head,&last);
      
      /*if pivot was not the smallest element*/
      if(mid != head)
      {
         /*Finds element preceeding the pivot*/ 
         node *before_mid = head;
         while(before_mid->next != mid)
            before_mid = before_mid->next;
         
         /*Partitions list at before_mid*/
         before_mid->next = NULL;
         
         /*Calls quicksort on first part of list*/
         head = quick_sort(head,before_mid);
         
         /*Combines all sorted parts of list*/
         last_node(head)->next = mid;
      }
      /*Calls quicksort for second part of list*/
      mid->next = quick_sort(mid->next,last);
   }
   return head;
}

/*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, 10);
  InsFront(&head, 9);
  InsFront(&head, 1);
  InsFront(&head, 3);
  InsFront(&head, 23);
 
  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Function to find last node*/
  node *last = last_node(head);
  
  /*Calling quick sort function*/
  head = quick_sort(head,last);
  cout<<"\nResultant Linked list is:\n";
  printList(head);
 
  return 0;
}

Output:

Created Linked list is:
23-> 3-> 1-> 9-> 10-> 8-> NULL
Resultant Linked list is:
1-> 3-> 8-> 9-> 10-> 23-> NULL

 Time Complexity to quicksort list: O(N2)
where N is the number of nodes in the list.
NOTE:
This complexity can be changed to O(NlogN) if par

Maximum Product Subarray

Maximum Product Subarray

In this post we deal with the problem of finding a maximum product subarray from the given input array.

Finding Maximum Product Subarray Problem Statement

Given an input array which is allowed to contain both positive and negative integers, we need to find the subarray that has the maximum product from the input array.

How to find maximum product subarray from given array Example

Input Array arr[] = { -1, -3 , -10, 0, 60 }
Output = 60 // The subarray is {60}
Input: arr[] = {6, -3, -10, 0, 2}
Output:   180  // The subarray is {6, -3, -10}

Maximum Product Subarray Problem Video Explanation

Find Maximum Product Subarray Problem Solution

This solution is similar to largest-sum-contiguous-subarray problem . The only thing to note here is, maximum product can also be obtained by minimum (negative) product ending with the previous element multiplied by this element.
For example, in array {12, 2, -3, -5, -6, -2}, when we are at element -2, the maximum product is multiplication of, minimum product ending with -6 and -2.

Maximum Product Subarray Problem Algorithm:

  1. Initialize maxEndingHere, minEndingHere and maxSoFar as 1.
  2. Traverse through the entire array
    1. If the elemnt is positive update maxEndingHere. minEndingHere is updated only if it was negative.
    2. If the element is 0,make both maxEndingHere and minEndingHere 0.
    3. If element is negative, Next minEndingHere will always be previous maxEndingHere * arr[i].
    4. next maxEndingHere will be 1 if previous minEndingHere is 1,otherwise it will be minEndingHere * arr[i].

Solution code in C++

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

// Utility functions to get minimum of two integers
int min (int x, int y) {return x < y? x : y; }
 
// Utility functions to get maximum of two integers
int max (int x, int y) {return x > y? x : y; }
 
/* Returns the product of max product subarray. 
   Assumes that the given array always has a subarray
   with product more than 1 */
int maxSubarrayProduct(int arr[], int n)
{
    // max positive product ending at the current position
    int maxEndingHere = 1;
 
    // min negative product ending at the current position
    int minEndingHere = 1;
 
    // Initialize overall max product
    int maxSoFar = 1;
 
    /* Traverse through the array. Following values are
       maintained after the i'th iteration:
       maxEndingHere is always 1 or some positive product
                       ending with arr[i]
       minEndingHere is always 1 or some negative product 
                       ending with arr[i] */
    for (int i = 0; i < n; i++)
    {
        /* If this element is positive, update max_ending_here. 
           Update minEndingHere only if minEndingHere is 
           negative */
        if (arr[i] > 0)
        {
            maxEndingHere = maxEndingHere*arr[i];
            minEndingHere = min (minEndingHere * arr[i], 1);
        }
 
        /* If this element is 0, then the maximum product 
           cannot end here, make both maxEndingHere and 
           minEndingHere 0
           Assumption: Output is alway greater than or equal 
                       to 1. */
        else if (arr[i] == 0)
        {
            maxEndingHere = 1;
            minEndingHere = 1;
        }
 
        /* If element is negative. This is tricky
           maxEndingHere can either be 1 or positive. 
           minEndingHere can either be 1 or negative.
           next minEndingHere will always be prev. 
           max_ending_here * arr[i] next max_ending_here
           will be 1 if prev minEndingHere is 1, otherwise 
           next maxEndingHere will be prev minEndingHere *
           arr[i] */
        else
        {
            int temp = maxEndingHere;
            maxEndingHere = max (minEndingHere * arr[i], 1);
            minEndingHere = temp * arr[i];
        }
 
        // update max_so_far, if needed
        if (maxSoFar <  maxEndingHere)
          maxSoFar  =  maxEndingHere;
    }
 
    return maxSoFar;
}
 
// Driver Program to test above function
int main()
{
    int arr[] = {1, -2, -3, 0, 7, -8, -2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Maximum Sub array product is "<<maxSubarrayProduct(arr, n);
    return 0;
}

 Output :

Maximum Sub array product is 112

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

Find a pair with the given difference in an array

Find a pair with the given difference in an array

In this post we deal with the question on how to find a pair with the given difference in an array.

Find a pair with the given difference in an array Problem Statement:

Given an unsorted array and a number n,we need to find if there exists a pair of elements in the array whose difference is n. We can solve the problem using three methods as described below.

How to Find a pair with the given difference in an array Problem Example:

Input arr[] = { 4, 57, 82, 19, 25 } , n = 63
Output = Pair found // (82,19)
Input arr[] = { 2, 67, 45, 9, 12 }, n = 20
Output = No Pair found

Find a pair with the given difference Problem Solution

Method 1:

In this we run two loops. The outer loop picks the first element (smaller element) and the inner loop looks for the element picked by outer loop plus n.

Algorithm:

  1. Run two loops.
  2. Outer loop picks Ist element.
  3. inner loop checks for element picked by outer plus n.

Find a pair with the given difference Problem Solution Code in C++:

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

/*Function to find a pair with the given difference*/
bool findPair(int arr[], int size, int n)
{
   /*Outer loop picks for smaller element*/
    for(int i = 0;i < n;i++)
    {
     /*Inner loop checks for pair*/
     for(int j = 0;j < n;j++)
      {
         if(arr[j] == arr[i] + n)
         {
           cout<<"Pair Found :"<<arr[i]<<" "<<arr[j];
           return true;
          }
      }
    }
    cout<<"Pair not found ";
    return false;
}
 
// Driver program to test above function
int main()
{
    int arr[] = {1, 8, 30, 40, 100};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 60;
    findPair(arr, size, n);
    return 0;
}

 Output :

Pair Found :40 100

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


Method 2:

The first step is to sort the array . The idea for second step is take two index variables i and j, initialize them as 0 and 1 respectively. Now run a linear loop. If arr[j] – arr[i] is smaller than n, we need to look for greater arr[j], so increment j. If arr[j] – arr[i] is greater than n, we need to look for greater arr[i], so increment i.

Algorithm:

  1. Sort the given array.
  2. Initialize i = 0 and j = 1.
  3. Traverse the array
    1. If arr[j] – arr[i] < n , increment j.
    2. If arr[j] – arr[i] > n , increment i.

Find a pair with the given difference Problem Solution Code in C++:

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

// The function assumes that the array is sorted 
bool findPair(int arr[], int size, int n)
{
    // Initialize positions of two elements
    int i = 0;  
    int j = 1;
 
    // Search for a pair
    while (i<size && j<size)
    {
        if (i != j && arr[j]-arr[i] == n)
        {
            cout<<"Pair Found:"<<arr[i]<<" "<<arr[j];
            return true;
        }
        else if (arr[j]-arr[i] < n)
            j++;
        else
            i++;
    }
 
    cout<<"No such pair";
    return false;
}
 
// Driver program to test above function
int main()
{
    int arr[] = {1, 8, 30, 40, 100};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 60;
    findPair(arr, size, n);
    return 0;
}

 Output :

Pair Found:40 100

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

Binary Heaps: Introduction

Binary Heaps: Introduction

A binary heap is a complete binary tree that satisfies the heap property.
A heap can be classified further as either a max heap or a min heap.
In a max heap, the keys of i.e. values held by parent nodes are always greater than or equal to those of the children and the highest key is in the root node.
In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node.
This relation between key values of parent and child nodes is known as the heap property.
The heap property does not mean that keys are in a sorted order like they are in BSTs.

Max Heap:

Min Heap:

 

Since heaps are complete binary trees, they can be stored using arrays without any space wastage.

Applications of Heaps:

  1. Heap Sort: Heap can be used to sort an array in O(nLogn) time.
  2. Priority Queue: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time.
  3. Graph Algorithms: Heaps are used to efficiently implement Graph Algorithms like Dijkstra’s shortest path and Prim’s minimum spanning tree.

Operations on Min Heap:

  1. getMin(): Returns the smallest element i.e. root element of Min Heap. Time Complexity of this operation is O(1).
  2. extractMin(): Removes the minimum element from Min Heap. Time Complexity of this Operation is O(Logn) as this operation needs to call heapify() to ensure that heap property is maintained.
  3. decreaseKey(): Decreases value of key. Time complexity of this operation is O(Logn) as we will need to ensure that heap property is maintained by invoking heapify().
  4. insert(): Inserts a new key. This also takes O(Logn) time as we will need to heapify() this key.
  5. delete(): Deletes a key. This also takes O(Logn) time.
    We replace the key to be deleted with minus infinity by calling decreaseKey(). After decreaseKey(), the minus infinity value will be at the root and we call extractMin() to remove it.

Hash Map

Introduction to Hash Map in C++

A hash map or a hash table is a data structure that stores values which are associated with keys. The key values are generally used to sort and uniquely identify the elements in the hash map, while the mapped values store the content associated to this key. The types of key and mapped value may differ. The mapped values in a map can be accessed directly using their keys.

Video tutorial for Hashmap:

Defining a Hash Map

Syntax:        map <datatype_of_key , datatype_of_value> name_of_map;

Example:      map <string,int> Employee

The above example defines a map data structure which contains keys of string type and corresponsing mapped values of integer type. This declaration uses a function predefined in the header file “map”. This example may describe a hash map that contains employee IDs (mapped values) which are mapped to each employee’s ID (key value).

Insertion in Hash Map

Insertion can be done in 3 ways.  Using the above mentioned example;

Employee["Neha"] =  1 ;

This insertion is quite similar to an array where the key value is used as the index and mapped value is the value at that index. So, this line of code will insert into map “Employee” a key value “Neha” and a mapped value “1” which is Neha’s ID.

Employee.insert (std::pair<string,int>("Neha",1));

The “std::pair” is a struct template that allows storage of two different data items as a single unit. Thus, “Neha” and “1” are combined into a single unit and inserted into the hash map through the “insert” function present in the “map” header file. The same can be achieved using “make_pair” which is defined in header “utility” i.e.
Employee.insert (std::make_pair(std::string(“Neha”),1));

Employee.insert (map<string,int>::value_type("Neha",1));

Similarly, this also stores the respective values an element of a map and then inserts them in the map “Employee”.

NOTE: Keys in a map are unique, hence, the insertion operation checks whether the key of the inserted element is equivalent to an existing one, and if so, the element is not inserted, returning an iterator to this existing element (if the function returns a value).

Iteration through a Map

Traversal of a map can be done using a for loop-

for(map<string,int>::iterator i = Employee.begin() ; i!= Employee.end() ; i++)
    cout<<(*i).first<<i->second;
  • “map<string,int>::iterator i” declares an iterator ‘i’ to elements of a map.
  • A map iterator points to the elements of type pair<string,int> i.e. objects whose first element is a string and second is an integer. Hence, an iterator will point to elements in a hash map.
  • “begin()” returns an iterator to the first element in the hash map “Employee”.
  • “end()” returns an iterator to past-the-end element in the hash map. This element is theoritical and points to no real element. Thus, using this condition the entire hash map starting from first element till the last element can be traversed.
  • “(*i).first” displays the key value of the element pointed to by the iterator, using the ‘dot'(.) operator.
  • “i->second” displays the mapped value of the element pointed to by the iterator, using the ‘arrow’ (->) operator.

Find element in Hash Map

map<string,int>::iterator i;
i = Employee.find("Neha");
cout<<i->second;
  • Line 1 declares an iterator.
  • Line 2 attempts to find an element in the map “Employee” with a key value equivalent to “Neha”. If this key value is found, an iterator to that element will be returned. Otherwise, a past-the-last element iterator will be returned to signify that the given key could not be found. The returned value is then stored in iterator i.
  • If the element is found, line 3 displays the mapped value of the element whose key is “Neha” which in this case will be “1”.

Sample Code:

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
   /*Declaring a map*/
   map<string,int> Emp;

   /*Inserting elements into hashmap using various methods*/
   Emp["Neha"] = 1;
   Emp.insert (std::pair<string,int>("Amit",2));
   Emp.insert (std::make_pair(std::string("Kunal"),3));
   Emp.insert (map<string,int>::value_type("Alka",4));
   
   /*Traversing and displaying hash map*/
   cout<<"Hash map is\n\n";
   for(map<string,int>::iterator i = Emp.begin() ; i!= Emp.end() ; i++)
    	cout<<(*i).first<<" : "<<i->second<<endl;
    	
   /*Find element in a map*/
   map<string,int>::iterator j;
   j = Emp.find("Sita");
   if(j != Emp.end())
      cout<<"\nFound ID of Sita: "<<j->second;
   else
      cout<<"\nKey "Sita" not found.";

   return 0;
}

 Output:

Hash map is

Alka : 4
Amit : 2
Kunal : 3
Neha : 1

Key not found.

Hashing: Introduction

Hashing: Introduction

Consider we need to store some information  about employees keyed using employee number in sorted fashion
We have the following data structures to store information:

  1. Array
  2. Linked List
  3. Balanced binary search tree
  4. Direct Access Table.

Arrays and linked lists
Search can be done in O(Logn) time using Binary Search.
But insertion and deletion will take O(n).

Balanced binary search tree
Search, deletion and insertion will take O(Logn) time.

Direct access table
We make a big array and use employee numbers as index in the array. An array element stores NIL if employee number is not present, else the array stores pointer to information about employee with corresponding employee number. Time complexity wise, we can do all operations in O(1) time.
But this solution has many practical limitations. First problem with this solution is extra space required is huge.
If employee number is 10 digits, we need: O(p * 1010) space where, p is size of a pointer to record.
Another problem is an integer in a programming language may not store 10 digits.

Hashing is the solution that can be used in almost all such situations as it solves the space requirement problem.
Hashing, when implemented properly, gives O(1) search time on average and O(n) in worst case.

Hashing is an improvement over Direct Access Table. The idea is to use hash function that converts a given key to a smaller number and uses the small number as index in a table called hash table.

Hashing is often implemented in two steps:

  1. The element to be stored i.e. employee number is converted into an integer called key using the Hash Function and that key is used as an index to store original element in the hash table.
  2. The element is stored in the hash table, where it can be quickly retrieved using hashed key.

In simple terms, a hash function maps a big number or string to a small integer that can be used as index in hash table.
A good hash function should:

  • Be able to compute keys efficiently.
  • Should distribute the keys uniformly in the hash table to get search time of O(1).

Hash Table is nothing but an array that stores pointers to records corresponding to a given employee number. An entry in hash table is NIL if no existing employee number has hash function value i.e. key value equal to the index for the entry.

Hashing Video Explanation:

Collision Handling
Since a hash function gets us a small number for a key which is a big integer or string, there is possibility that two elements result in same key value.
This situation where a newly inserted key maps to an already occupied slot in hash table is called collision and must be handled using some collision handling technique.
Following are the ways to handle collisions:

  • Chaining: Elements that have the same hash function value i.e. key values are chained onto a common linked list of records.
    There is one linked list corresponding to all possible key values. Chaining is simple, but requires additional memory outside the table.
  • Open Addressing: In open addressing, all elements are stored in the hash table itself.
    Each table entry contains either a record or NIL. When searching for an element, we one by one examine table slots until the desired element is found or it is clear that the element is not in the table.