Category Archives: Algorithms

Union-Find Algorithm

Posted on by 
Detect Cycle in a an Undirected Graph

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Union: Join two subsets into a single subset.
        0
        |  \
        |    \
        1-----2
For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.
Initially, all slots of parent array are initialized to -1 (means there is only one item in every subset). 
0   1   2
-1 -1  -1 
Edge 0-1: Find the subsets in which vertices 0 and 1 are. Since they are in different subsets, we take the union of them. For taking the union, either make node 0 as parent of node 1 or vice-versa. 
0   1   2     <---- 1 is made parent of 0 
                    (1 is now representative of subset {0, 1})
1  -1  -1     
Edge 1-2: 1 is in subset 1 and 2 is in subset 2. So, take union. 
0   1   2    <----- 2 is made parent of 1 
                   (2 is now representative of subset {0, 1, 2})
1   2  -1
Edge 0-2: 0 is in subset 2 and 2 is also in subset 2. Hence, including this edge forms a cycle.
How subset of 0 is same as 2?
0->1->2 // 1 is parent of 0 and 2 is parent of 1

CODE
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
 
    return subsets[i].parent;
}
 
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
 
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
 
int isCycle( struct Graph* graph )
{
    int V = graph->V;
    int E = graph->E;
 
    struct subset *subsets =
        (struct subset*) malloc( V * sizeof(struct subset) );
 
    for (int v = 0; v < V; ++v)
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
 
    for(int e = 0; e < E; ++e)
    {
        int x = find(subsets, graph->edge[e].src);
        int y = find(subsets, graph->edge[e].dest);
 
        if (x == y)
            return 1;
 
        Union(subsets, x, y);
    }
    return 0;
}

Remove duplicate from unsorted linked list

Posted on by 
METHOD 1 (Using two loops)
 
struct node
{
 int data;
 struct node *next;
};
 
void removeDuplicates(struct node *start)
{
  struct node *ptr1, *ptr2, *dup;
  ptr1 = start;
 
  while(ptr1 != NULL && ptr1->next != NULL)
  {
     ptr2 = ptr1;
 
     while(ptr2->next != NULL)
     {
       
       if(ptr1->data == ptr2->next->data)
       {
          
          dup = ptr2->next;
          ptr2->next = ptr2->next->next;
          free(dup);
       }
       else 
       {
          ptr2 = ptr2->next;
       }
     }
     ptr1 = ptr1->next;
  }
}
 
Time Complexity: O(n^2)
 
METHOD 2 (Use Sorting)
In general, Merge Sort is the best suited sorting algorithm for sorting linked lists efficiently.
1) Sort the elements using Merge Sort. O(nLogn)
2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List. O(n)
Please note that this method doesn’t preserve the original order of elements.
Time Complexity: O(nLogn)

METHOD 3 (Use Hashing)
void deleteDups(LinkedListNode n)
 { 
      Hashtable table = new Hashtable();
      LinkedListNode previous = null;
      while (n != null) {
          if (table.containsKey(n.data)) 
              previous.next = n.next;
                          
          else {
              table.put(n.data, true);
              previous = n;
              }
              n = n.next;
      }
 }

Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).

Find k closest elements to a given value

Posted on by 
Runtime: O(Logn + k)

int findCrossOver(int arr[], int low, int high, int x)
{
if (arr[high] <= x)
return high;
if (arr[low] > x)
return low;

int mid = (low + high)/2;
if (arr[mid] <= x && arr[mid+1] > x)
return mid;

if(arr[mid] < x)
return findCrossOver(arr, mid+1, high, x);
return findCrossOver(arr, low, mid - 1, x);
}

void printKclosest(int arr[], int x, int k, int n)
{
int l = findCrossOver(arr, 0, n-1, x);
int r = l+1; // Right index to search
int count = 0; 

if (arr[l] == x) l--; // Assumption: all elements in arr[] are distinct

while (l >= 0 && r < n && count < k)
{
if (x - arr[l] < arr[r] - x)
printf("%d ", arr[l--]);
else
printf("%d ", arr[r++]);
count++;
}

while (count < k && l >= 0)
printf("%d ", arr[l--]), count++;

while (count < k && r < n)
printf("%d ", arr[r++]), count++;
}

Sort n numbers in range from 0 to n^2 – 1 in O (n)

Posted on by 
Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers. 
Since n2-1 is the maximum possible value, the value of d would be O(logb(n)). 

So overall time complexity is O((n + b) * logb(n)).
If we set b as n, the value of O(logb(n)) becomes O(1) and overall time complexity becomes O(n).

// the digit represented by exp.
int countSort(int arr[], int n, int exp)
{
 
    int output[n];
    int i, count[n] ;
    for (int i=0; i < n; i++)
       count[i] = 0;
 
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%n ]++;
 
    for (i = 1; i < n; i++)
        count[i] += count[i - 1];
 
    for (i = n - 1; i >= 0; i--)
        output[--count[ (arr[i]/exp)%n]] = arr[i];

    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

void sort(int arr[], int n)
{
    // Do counting sort for first digit in base n. 
       exp (n^0 = 0) is passed.
    countSort(arr, n, 1);
 
    // Do counting sort for second digit in base n. 
       exp (n^1 = n) is passed.
    countSort(arr, n, n);
}

How to sort if range is from 1 to n2 ?
1) Subtract all numbers by 1.
2) Since the range is now 0 to n2, do counting sort twice as done in the above implementation.
3) After the elements are sorted, add 1 to all numbers to obtain the original numbers.

How to sort if range is from 0 to n^3 -1?
Since there can be 3 digits in base n, we need to call counting sort 3 times.

Search in an almost sorted array

Posted on by 
int binarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;
 
        // If the element is present at one of the middle 3 positions
        if (arr[mid] == x)  return mid;
        if (mid > l && arr[mid-1] == x) return (mid - 1);
        if (mid < r && arr[mid+1] == x) return (mid + 1);
 
        if (arr[mid] > x) return binarySearch(arr, l, mid-2, x);
 
        return binarySearch(arr, mid+2, r, x);
   }
       return -1;
}

When does the worst case of Quicksort occur?

Posted on by 
The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, 
the worst occurs in following cases.

1) Array is already sorted in same order.
2) Array is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2) 

Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition 
or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. 
With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur 
if the input array is such that the maximum (or minimum) element is always chosen as pivot.

How is the complexity of bucket sort is O(n+k) if we implement buckets using linked lists?

Posted on by 
Right now, you are correct that iterating across the input array to distribute the elements into buckets takes time O(n). 
However, you are slightly off when you say that the total amount of time required to assemble the array is O(k * (average number of elements per bucket)). 
Note that because there are n elements and k buckets, this would come out to O(k * (n / k)) = O(n), for a total runtime of O(n). 

It is not true that k * O(n / k) = O(n). The reason for this is that the term O(n / k) is hiding a constant factor. 
When you visit each bucket and take a look at the elements it contains, it doesn't take exactly n / k time, or even some constant multiple of n / k time. 

For example, what happens if the bucket is empty? In that case, you're still spending some amount of time looking at the bucket, 
since you have to determine that you shouldn't iterate over its elements. 

Thus a more accurate representation of the time required per bucket is something like c0(n / k) + c1, where c0 and c1 are implementation-specific constants. 
This expression is, of course, O(n / k).

The catch is what happens when you multiply this expression by k to get the total amount of work done. 
If you compute k * (c0(n / k) + c1)
You get c0n + c1k
As you can see, this expression depends directly on k, so the total runtime is O(n + k).

Count Inversions in an array

Posted on by 
int *temp = (int *)malloc(sizeof(int)*array_size);  

int mergeSort(int arr[], int temp[], int left, int right)
{
   int count = 0;
  if (right > left)
  {
int mid = (right + left)/2;
      count = mergeSort(arr, temp, left, mid);
      count += mergeSort(arr, temp, mid+1, right);
      count += merge(arr, temp, left, mid, right);
  }
return count;
}
  
int merge(int arr[], int temp[], int left, int mid, int right)
{
  int i, j, k;
  int count1 = 0;
  i = left;
  j = mid+1; 
  k = left;
  
   while ((i <= mid) && (j <= right))
   {
    if (arr[i] <= arr[j])
    {
      temp[k++] = arr[i++];
    }
    else
    {
      temp[k++] = arr[j++];
      count1 += (mid - i);
    }
  }
  
  while (i <= mid)
    temp[k++] = arr[i++];
  
  while (j <= right)
    temp[k++] = arr[j++];
  
  for (i=left; i <= right; i++)
    arr[i] = temp[i];
  }

Queue using linkedlist

Posted on by 
 struct Queue
 {
        int Data;
        struct Queue* next;
 }*rear, *front;

void enqueue (int value)
{
    if (rear == NULL)
    {
        rear = (struct Queue *) malloc(sizeof(struct Queue));
        rear->next = NULL;
        rear->Data = value;
        front = rear;
    }
    else
    {
        temp = (struct Queue *)malloc(sizeof(struct Queue));
        rear->next = temp;
        temp->Data = data;
        temp->next = NULL;
 
        rear = temp;
    }
}

void dequeue()
{
    front1 = front;
 
    if (front1 == NULL)
    {
        printf(" Error: Trying to display elements from empty queue");
        return;
    }
    else
        if (front1->next != NULL)
        {
            printf("Dequed value : %d", front1->Data);
            front1 = front1->next;
            free(front);
            front = front1;
        }
        else
        {
            printf("Dequed value : %d", front->Data);
            free(front);
            front = NULL;
            rear = NULL;
        }
}

void display()
{
     struct Node *var = rear;
     if(var == NULL)
        printf("\nQueue is Empty");
     else
     {
        while(var!=NULL)
        {
           printf("%d",var->Data);
           var=var->next;
         }
     }      
}

Queue using array

Posted on by 
#define MAX 10
int queue[MAX], front=-1, rear=-1;

void enqueue (int num)
{
  if(front == 0 && rear == MAX-1)
    printf("Queue OverFlow Occured");
  
  else if(front == -1 && rear == -1)
  {
      front = rear = 0;
      queue[rear] = num;
  }

  else if(rear == MAX-1 && front != 0)
  {
    rear = 0;
    queue[rear] = num;
  }
  else
  {
      rear++;
      queue[rear] = num;
  }
}

void dequeue()
{
  if(front == -1)
  {
      printf("Underflow");
      return
  }
  int element = queue[front];
  if(front == rear)
     front = rear = -1;
  if(front == MAX-1)
     front = 0;
  else
     front++;
    
   printf("The deleted element is: %d", element);
}