How to Shuffle an Array or the Fisher-Yates Algorithm

Question: how can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5).

Solution: this problem can be solved using Knuth Shuffling Algorithm a.k.a Fisher-Yates Shuffling Algorithm. The core strategy behind the algorithm is to pick a random index between 0 and N, where N is the greatest index of the unshuffled array, and then move that element to the shuffled part of the array. In other words, the algorithm partitions the original array into two parts, the unshuffled and shuffled part. It randomly picks an element from the unshuffled part and puts it into the shuffled part. It does that until no elements left in the unshuffled part. Here is the implementation in C:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void knuthShuffle(int orgArray[], int arraySize)
{
   if (arraySize == 0 || arraySize == 1)
      return;

   srand(time(NULL));

   int i;
   int index, temp;
   for (i = arraySize - 1; i > 0; i--)
   {
      index = rand() % (i+1);
      temp = orgArray[index];
      orgArray[index] = orgArray[i];
      orgArray[i] = temp;
   }
}

Explanation: in order to partition the array, we traverse the array from the end to start. The subarray from iterator index i to the last index of the array (arraySize - 1) is the shuffled part. And, the subarray from the first index (0) to the iterator index i is the unshuffled part. As, the index i moves up the array, we randomly generate a number between 0 and i + 1 using C-function rand(). We then swap the element at the index that equals the random number with the element at the last index (i) of the unshuffled part. As the result of decreasing i by 1 for every loop iteration, the partitions are automatically reserved. Here is an example with illustration that will hopefully make everything clearer.

Example: we'll shuffle this array(1, 2, 3, 4, 5). Notice that the value for index is randomly picked, so at run time the algorithm may not generate the values in the exact order that they are here. We just need to understand that, the random values are always greater than or equal 0 and less than i. Here is what the array starts out with:

1. First iteration, i = arraySize - 1 = 4. Let's say that index is randomly generated as 3, so we switch array[3] with array[4]. Here is the picture:
   
   



2. Second iteration, decrement i by 1, so i = 3 and index randomly generated as 0. We swap array[0] and array[3]:
   
   



3. Third iteration, i = 2 and index = 1. Swap array[2] with array[1].
   
   



4. Fourth iteration, i = 1 and index = 0. Swap array[0] and array[1].
   
   



5. Fifth iteration: i = 0, so loop terminates. Nothing happens. Here is the final shuffled array:
   
   

If there is any bug or better solution, please let me know in the comment section below. Thanks for reading :)

Sorting Array of Three Kinds or The Dutch National Flag Problem

Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), write an algorithm to sort the array. For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c).

Solution: the Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors. Hence, we can adopt the algorithm to sort any array of three different kinds of objects / values. Let's take a look at the implementation below where we sort an array of three different integers:

void dutchFlagSort(int inArray[], int arraySize, int high, int low)
{
  if (arraySize == 0)
    return;

  int lower = 0;
  while (inArray[lower] == low && lower < arraySize)
    lower++;

  int upper = arraySize - 1;
  while (inArray[upper] == high && upper >= 0)
    upper--;

  int temp = 0;
  int pivot;
  for (pivot = lower; pivot <= upper;)
  {
    if (inArray[pivot] == low)
    {
      temp = inArray[pivot];
      inArray[pivot] = inArray[lower];
      inArray[lower] = temp;
      pivot++;
      lower++;
    }
    else if (inArray[pivot] == high)
    {
      temp = inArray[pivot];
      inArray[pivot] = inArray[upper];
      inArray[upper] = temp;
      upper--;
    }
    else
      pivot++;
  }
}

Explanation: the method above takes in an array of integers, the array's size, and the order of the integers (low and high) as arguments. Notice that low indicates the lowest value in the array and high indicates the highest value in the array. For example, if our array is (1, 2, 3, 1, 2, 3) then the low maybe 1 and high maybe 3. The algorithm uses those indicators to sort the array. We can actually specify low and high as any value in the array if we want to. It only affects how the array places the integers.

The basic strategy behind the method is to partition the array into three regions, low, middle and high. These regions correspond to the three kinds of integers. Low integers whose values equal low, high integers whose values equal high, and the middle integers whose values are anything other than high and low.

That's why we have three different iterators. Any integer before lower is low integer, and any integer after upper is high integer. The pivot iterator traveses the array and swaps high and low integers to their correct places. However, it skips over the middle integers because they are supposed to be in the region between low and high integer regions. Let's do an example to clear things up.

Example: lets Dutch Flag sort this array (0, 2, 1, 0, 1, 2)

1. low = 0, high = 2
2. After the first while loop, lower = 1. After the second while loop, upper = 4. Finally, pivot = 1.
   
   



3. Entering the for loop:
   
   First iteration: array[pivot] = 2 (high), so we swap array[pivot] with array[upper] and decrease upper by 1.
   
   
   
   
   Second iteration: pivot = 1, lower = 1, and upper = 3. Because array[pivot] = 1, we do nothing but increasing pivot by 1.
   
   
   
   
   Third iteration: pivot = 2, lower = 1, and upper = 3. Again, array[pivot] = 1, we just increase pivot by 1 and move on.
   
   
   
   
   Fourth iteration: pivot = 3, lower = 1, and upper = 3. Since array[pivot] = 0 (low), we swap array[pivot] and array[lower]. Then, we increase both pivot and lower by 1.
   
   
   
   
   Fifth iteration: pivot = 4, lower = 2, and upper = 3. The loop terminates here because pivot is now greater than upper. Here is the final array. Notice how all the 0s, 1s and 2s are separated and sorted in ascending order.
   
   
   
   
   
   

Well, I hope everything is clear now after the example. If you have any question, please feel free to post it in the comment section below.

Calculate the Least Common Multiple of Two Integers

Question: write an algorithm to return the least common multiple (LCM) of two integers. For example, if the inputs are 3 and 4, the function returns 12.

Solution: least common multiple (LCM) is the lowest value that is a multiple of both integers. That means LCM is divisible by both integers or the modulus of LCM divided by either integers is 0 (LCM % num = 0). Thus, we just need to start with a reasonable number and keep increasing that number until it is divisible by both integers. The number is then the LCM of the integers.

But where is the reasonable number to start out? Well, instead of starting out at 1, we can start out at the highest integer between the two integers. The reason is that a number that is less than either of those two integers can't be divisible by those integers. For example, if we are to find LCM of 2 and 3, then any number that is less than 3 is surely not the LCM. Thus, we can safely start our search at 3. Notice that one integer can be the LCM of another integer. That's why we start out at the higher number. For example, the LCM of 2 and 4 is 4. Here is the algorithm in C:

  int lcm(int num1, int num2)
  {
    if (num1 % num2 == 0)
      return num1;

    if (num2 % num1 == 0)
      return num2;
      
    int n = (num1 <= num2) ? num2 : num1;
    
    for (; ; n++)
    {
      if(n % num1 == 0 && n % num2 == 0)
         return n;
    }
  }

Explanation: our function takes two integers as arguments and returns the LCM of those integers.

1. First, we take the modulus of the first integer (num1) and the second integer (num2). If num1 % num2 equals 0, we know num1 is the LCM because num1 is divisible by num1 and is the smallest number that is not less than num1 and num2. Similarly, if num2 % num1 equals 0 then num2 is the LCM.
2. When neither integer is the LCM, we find out which integer is greater and begin to find the LCM starting from that integer. That's exactly what the for loop does. For every iteration, we increase n by 1 until we find a number that divisible by both num1 and num2. This loop guarantees to find the solution. That's why we don't need any other return statement outside the loop. Nor we need a termination condition for the loop.

That's all we have for today. Thanks for reading!

Convert Binary Tree to Double Linked List

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:

The output will be a double linked list like this:

Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list.

For traversing the tree, we'll use level / order traversal a.k.a breadth first search. If you are not familiar with that concept, here is the post for you :) Take your time to read it, I'll be right here when you come back!

To construct the linked list, each node will have its left pointer point to the node in front of it and its right pointer point to the node behind it in the linked list. For instance, if node 1 is in front of node 2 and node 3 is behind node 2 in the linked list, we'll set left pointer of node 2 to node 1 and right pointer of node 2 to node 3 (see picture above)

#include<iostream>
#include<queue>
using namespace std;

struct Node
{
  int data;
  struct Node* left;
  struct Node* right;
};

struct Node* bt2DoubleLinkedList(struct Node* root)
{
  if (root == NULL)
    return NULL;

  queue nodeQueue;

  struct Node* head = root; //reference to head of the linked list
  struct Node* listIT = NULL; //current node being processed
  struct Node* prevNode = NULL; //previous node processed

  //initialize the stack
  nodeQueue.push(root);

  //convert to double linked list
  while (!nodeQueue.empty())
  {
    //process next node in stack
    prevNode = listIT; 
    listIT = nodeQueue.front();
    
    nodeQueue.pop();

    //add left child to stack
    if (listIT->left != NULL)
      nodeQueue.push(listIT->left);

    //add right child to stack
    if (listIT->right != NULL)
      nodeQueue.push(listIT->right);

    //add current node to linked list
    if (prevNode != NULL)
      prevNode->right = listIT;
    listIT->left = prevNode;
  }
  
  //connect end node of list to null
  listIT->right = NULL;

  return head;
}

Explanation: the method accepts a pointer to the tree's root as argument and returns the pointer to the head node of the linked list:

1. If the root node is null, we return null because the tree is empty.
2. If the root is not null, we proceed by first creating a queue to store the the nodes. Why do we use queue? That is how we traverse the tree by level. Every time we reach a node, we store its children in the queue for later processing. Thus, the queue will always have something in it as long as there are still unvisited node in the tree.
3. Next, we create three pointers. head points to the head node of the linked list. listIT is our list iterator which used to build the list one node at a time. prevNode is the last node added into the list. We need to keep track of such node because we have to change the right pointer of that node to the node immediate after it, which is the node that listIT will point to.
4. We initialize the queue by adding the root into it. The reason is that we will use the condition of empty queue to end the while loop.
5. The while loop will run until no node left in queue to process. For each node in the queue, we do the following:
   
   prevNode = listIT gets reference to the last processed node because we are about to process a new node
   
   listIT = nodeQueue.front() gets reference to the top in the queue because we're going to add it into the list.
   
   nodeQueue.pop() removes the top node out of the queue.
   
   We then add the left and right child of the top node into the queue, so we can process them later. Notice that we only add the children if they are not null.
   
   Finally, we connect the top node to the linked list. First, we set the right pointer of the previous node (prevNode) to the top node. Then, we set the left pointer of the top node to the previous node. As the result, the top node becomes the end node of the linked list and the previous node completely breaks off the tree.
   
   
6. When the last node is added into the linked list and the while loop exits, we have a double linked list. The only thing left is to set the end node's right pointer (pointed to by listIT) to null because there is no more node to add into the list.

Whew! That was a long explanation. If you are still confused, you may want to read about breadth first traversal and do an example with pencil and paper. Also, please don't hesitate to ask questions in the comment section below!