## Sort a linked list containing 3 different types of elements

Question 46. Given a linked list where the nodes can have the values 0 or 1 or 2, sort it in a single pass. For instance 2->1->0->0->2->0>1 should be sorted as 0->0->0->1->1->2->2

To sort the linked list in a single pass, we make use of the fact that there are only 3 possible values for the nodes in the linked list. So as we traverse the linked list, we can remove the nodes from the original linked list and append them into 3 separate linked lists based on the value of the nodes. At the end we can merge the 3 linked lists. The procedure we can use to solve the problem is as follows

1. Maintain the head and tail pointers for linked list-0 (will contain nodes with value 0), linked list-1 (will contain nodes with value 1) and linked list-2 (will contain nodes with value 2)

2. As we traverse through the original linked list, remove each node from the original linked list and add it to linked list-0 or linked list-1 or linked list-2 based on the value of the node.

## C/C++

```
/*
tail: array of tail pointers of the separated lists
cur_node: current node being processed
i: data value of the node
*/
struct node *cur_node, int i)
{
if (!tail[i])
tail[i] = cur_node;

}

/*first_node: first node in list to be sorted
num_distinct_values: number of distinct values in the nodes
Return value: head of the sorted list
*/
struct node * sort_list(struct node *first_node, int num_distinct_values)
{
struct node *result = NULL, *cur_node, *next_node, *last_element;
int i;

if (!first_node)
return NULL;

head = (struct node**) calloc(num_distinct_values, sizeof(struct node*));
tail = (struct node**) calloc(num_distinct_values, sizeof(struct node*));

for (i = 0; i < num_distinct_values; ++i) {
tail[i] = NULL;
}

/*Partition the list into separate lists, (0-list, 1-list, 2-list)
based on the data in the node*/
cur_node = first_node;
while (cur_node) {
next_node = cur_node->next;
cur_node = next_node;
}

and so on*/
last_element = tail[0];
for (i = 1; i < num_distinct_values; ++i) {
if (!result)

if (last_element)

/*update the last element to the tail of current list*/
if (tail[i])
last_element = tail[i];
}

free(tail);

return result;
}

```

## Java

```
/*
tail: array of tails of the separated lists
curNode: current node being processed
i: data value of the node
*/
if (tail[i] == null)
tail[i] = curNode;

}

/*firstNode: first node in the list to be sorted
numDistinctValues: number of distinct values
Return value: head of the sorted list
*/
int numDistinctValues) {

if (firstNode == null)
return null;

int i;
for (i = 0; i < numDistinctValues; ++i) {
tail[i] = null;
}

/*Partition the list into separate lists (0-list, 1-list and 2-list)
based on the data in the node*/
while (curNode != null) {
curNode = nextNode;
}

and so on*/
for (i = 1; i < numDistinctValues; ++i) {
if (result == null)

if (lastElement != null)

/*update the last element to the tail of current list*/
if (tail[i] != null)
lastElement = tail[i];
}

return result;
}

```

## Python

```
#tail: list having tail nodes of all the separated linked lists
#cur_node: current node being processed
#i: data value of the node
@staticmethod
if (tail[i] == None):
tail[i] = cur_node

#first_node:  first node in the linked list to be sorted
#num_distinct_values: number of distinct values
@staticmethod
tail = [None] * num_distinct_values
result = None

if (not first_node):
return None

#(0-list, 1-list and 2-list) based on the data in the node
cur_node = first_node
while (cur_node) :
next_node = cur_node.next
cur_node = next_node

#and so on
last_element = tail[0]
for  i in range(1, num_distinct_values):
if (not result):

if (last_element):

#update the last element to the tail of current linked list
if (tail[i] != None):
last_element = tail[i]

return result

```

I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

/

## Merge M sorted arrays

Question 45. Given m sorted arrays each of which has a size n, merge the arrays in sorted order into a single array of size m*n

To efficiently solve the problem we use a heap which has a maximum size of m (number of sorted arrays). If the arrays are sorted in non-decreasing order, then we maintain a min heap otherwise we maintain a max heap. The algorithm is as follows

1. Pick the first element from each array, add it to the heap and construct the heap using the heapify function

2. Add the topmost element in the heap to the result array. Then replace the topmost element of the heap with the next element from the same array as the topmost element. Re-adjust the heap using the heapify function. Suppose all elements in the same array are over, then add a MAX_INT for non-decreasing order (MIN_INT for non-increasing order) into the root of the heap and re-adjust the heap using heapify. Repeat this step until all elements in all the arrays are processed.

Inserting an element into a heap of size m takes O(logm). Since we have n*m elements, the time complexity of this approach is O(nm * logm).

The code for merging k sorted lists is given below.

## C/C++

```
/*
arrays: the arrays to be merged. arrays[0] has the first array, arrays[1] has
the second array and so on
n: number of elements in each array
k: number of arrays
result: the merged results are passed back in this array
*/
void merge_k_sorted_arrays(int arrays[][MAX_NUM_ELEMENTS], int n, int k,
int *result)
{
struct node *heap = (struct node*) calloc(k, sizeof(struct node));
int *arr_pos = (int*) calloc(k, sizeof(int));
int i, pos, res_index, array_no;

/*Store the first element in each array into the heap*/
for (i = 0; i < k; ++i) {
heap[i].value = arrays[i][0];
heap[i].array_no = i;
arr_pos[i] = 1;
}

/*Construct the initial heap using the heapify procedure*/
for (i = k - 1; i >= 0; --i)
heapify(heap, i, k);

/*
Process the remaining elements in the arrays. When all elements in the
arrays have been processed, MAX_INT will be present at root of heap
*/
res_index = 0;
while (heap[0].value != MAX_INT) {
/*
root of the heap will have the lowest value. So store
it into the result
*/
result[res_index++] = heap[0].value;

array_no = heap[0].array_no;
pos = arr_pos[array_no];

/*
If the root belongs to array x, then replace the root with
the next element in array x
*/
if (pos >= n) {
/*If we have exhausted all elements in the array,
then insert MAX_INT into the heap*/
heap[0].value = MAX_INT;
heap[0].array_no = array_no;
} else {
heap[0].value = arrays[array_no][pos];
heap[0].array_no = array_no;
}

/*Re-adjust the heap after replacing the root*/
heapify(heap, 0, k);

arr_pos[array_no]++;
}

free(arr_pos);
free(heap);
}

/* Helper function to perform heapify
heap: min heap.  Maximum number of elements in heap is k
pos: position of the heap that may need to be fixed
heap_size: current number of nodes in the heap
*/
void heapify(int heap[], int pos, int heap_size)
{
int left = 2 * pos;
int right = (2 * pos) + 1;
int ix_of_smallest = pos;

/*Find which of the three are the smallest: heap[pos] OR left child
OR right child*/
if (left < heap_size && heap[pos] > heap[left])
ix_of_smallest = left;
if (right < heap_size && heap[ix_of_smallest] > heap[right])
ix_of_smallest = right;

if (ix_of_smallest != pos) {
/*
If pos doesn't contain the smallest value,
then swap the smallest value into pos
*/
int temp = heap[pos];
heap[pos] = heap[ix_of_smallest];
heap[ix_of_smallest] = temp;

heapify(heap, ix_of_smallest, heap_size);
}
}

```

## Java

```
/*
arrays: the arrays to be merged. arrays[0] has the first array, arrays[1] has
the second array and so on
Return value: the merged results are passed back in this array
*/
public static int[] mergeKSortedArrays(int[][] arrays) {
int k = arrays.length;	/*number of arrays*/
int n = arrays[0].length; /*number of elements in each array*/
Node[] heap = new Node[k];
int[] arrPos = new int[k];
int[] result = new int[k * n];

/*Store the first element in each array into the heap*/
int i;
for (i = 0; i < k; ++i) {
heap[i] = new Node();
heap[i].value = arrays[i][0];
heap[i].arrayNo = i;
arrPos[i] = 1;
}

/*Construct the initial heap using the heapify procedure*/
for (i = k - 1; i >= 0; --i)
heapify(heap, i, k);

/*
Process the remaining elements in the arrays. When all elements in the
arrays have been processed, MAX_INT will be present at root of heap
*/
int resIndex = 0;
while (heap[0].value != MAX_INT) {
/*
root of the heap will have the lowest value. So store
it into the result
*/
result[resIndex++] = heap[0].value;

int arrayNo = heap[0].arrayNo;
int pos = arrPos[arrayNo];

/*
If the root belongs to array x, then replace the root with
the next element in array x
*/
if (pos >= n) {
/*If we have exhausted all elements in the array,
then insert MAX_INT into the heap*/
heap[0].value = MAX_INT;
heap[0].arrayNo = arrayNo;
} else {
heap[0].value = arrays[arrayNo][pos];
heap[0].arrayNo = arrayNo;
}

/*Re-adjust the heap after replacing the root*/
heapify(heap, 0, k);

arrPos[arrayNo]++;
}

return result;
}

/* Helper function to perform heapify
heap: min heap.  Maximum number of elements in heap is k
pos: position of the heap that may need to be fixed
heapSize: current number of nodes in the heap
*/
public static void heapify(int[] heap, int pos, int heapSize) {
int left = 2 * pos;
int right = (2 * pos) + 1;
int ixOfSmallest = pos;

/*Find which of the three are the smallest - heap[pos] OR left child
OR right child*/
if (left < heapSize && heap[pos] > heap[left])
ixOfSmallest = left;
if (right < heapSize && heap[ixOfSmallest] > heap[right])
ixOfSmallest = right;

if (ixOfSmallest != pos) {
/*
If pos doesn't contain the smallest value,
then swap the smallest value into pos
*/
int temp = heap[pos];
heap[pos] = heap[ixOfSmallest];
heap[ixOfSmallest] = temp;

heapify(heap, ixOfSmallest, heapSize);
}
}

```

## Python

```
#lists:  the lists to be merged. lists[0] has the first list, lists[1] has
#		the second list and so on
#Return value:  the merged results are passed back in this list
def merge_k_sorted_lists(lists) :
k = len(lists)	#number of lists
n = len(lists[0]) #number of elements in each list
heap = []
arr_pos = []

#Store the first element in each list into the heap
for  i in range(0, k):
new_node = Node()
new_node.value = lists[i][0]
new_node.list_no = i
heap.append(new_node)
arr_pos.append(1)

#Construct the initial heap using the heapify procedure
for  i in range(k - 1, -1,-1):
heapify(heap, i, k)

#Process the remaining elements in the lists. When all elements in
#the lists have been processed, MAX_INT will be present at root of heap
result = []
while (heap[0].value != MAX_INT) :
#root of the heap will have the lowest value. So store
#it into the result
result.append(heap[0].value)

list_no = heap[0].list_no
pos = arr_pos[list_no]

#If the root belongs to list x, then replace the root with
#the next element in list x
if (pos >= n) :
#If we have exhausted all elements in the list,
#then insert MAX_INT into the heap
heap[0].value = MAX_INT
heap[0].list_no = list_no
else :
heap[0].value = lists[list_no][pos]
heap[0].list_no = list_no

#Re-adjust the heap after replacing the root
heapify(heap, 0, k)

arr_pos[list_no] += 1

return result

#Helper function to perform heapify
#heap: min heap.  Maximum number of elements in heap is k
#pos: position of the heap that may need to be fixed
#heap_size: current number of nodes in the heap
def heapify(heap, pos, heap_size) :
left = 2 * pos
right = (2 * pos) + 1
ix_of_smallest = pos

#Find which of the three are the smallest - value at pos OR left child
#OR right child
if (left < heap_size and heap[pos] > heap[left]):
ix_of_smallest = left
if (right < heap_size and heap[ix_of_smallest] > heap[right]):
ix_of_smallest = right

if (ix_of_smallest != pos) :
#If pos doesn't contain the smallest value,
#then swap the smallest value into pos
heap[pos], heap[ix_of_smallest] = heap[ix_of_smallest], heap[pos]

heapify(heap, ix_of_smallest, heap_size)

```

I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

/

## Merge a small sorted array into a larger sorted array

Question 44. Given a small array of size n having n sorted elements and a big array of size m+n having m sorted elements at the beginning of the big array, merge the two arrays and store them in the big array

There is just enough free space in the big array to accommodate the elements of the small array. The two sorted arrays can be merged in O(m+n). The trick is to start filling up the big array from the end where the free space is present. The code for this is given below

## C/C++

```
/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
void merge_arrays(int a[], int b[], int m, int n)
{
int i, j, fill_pos;

i = m - 1;
j = n - 1;
fill_pos = m + n - 1; /*Start filling from the rear of the array*/

while (i >= 0 && j >= 0) {
if (a[i] > b[j]) {
a[fill_pos--] = a[i--];
} else {
a[fill_pos--] = b[j--];
}
}

/*Fill up the remaining elements of array a if any*/
while (i >= 0)
a[fill_pos--] = a[i--];

/*Fill up the remaining elements of array b if any*/
while (j >= 0)
a[fill_pos--] = b[j--];

}

```

## Java

```
/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
public static void mergeArrays(int[] a, int[] b, int m, int n) 	{
int i = m - 1;
int j = n - 1;
int fillPos = m + n - 1; /*Start filling from the rear of the array*/

while (i >= 0 && j >= 0) {
if (a[i] > b[j]) {
a[fillPos--] = a[i--];
} else {
a[fillPos--] = b[j--];
}
}

/*Fill up the remaining elements of array a if any*/
while (i >= 0)
a[fillPos--] = a[i--];

/*Fill up the remaining elements of array b if any*/
while (j >= 0)
a[fillPos--] = b[j--];
}

```

## Python

```
#a: list of size m+n which has m elements at beginning
#b: list of size n with n elements
#m: number of elements in list a
#n: number of elements in list b
def merge_lists(a, b, m, n) :
i = m - 1
j = n - 1
fill_pos = m + n - 1 #Start filling from the rear of list a

while (i >= 0 and j >= 0) :
if (a[i] > b[j]) :
a[fill_pos] = a[i]
fill_pos -= 1
i -= 1
else :
a[fill_pos] = b[j]
fill_pos -= 1
j -= 1

#Fill up the remaining elements of list a if any
while (i >= 0):
a[fill_pos] = a[i]
fill_pos -= 1
i -= 1

#Fill up the remaining elements of list b if any
while (j >= 0):
a[fill_pos] = b[j]
fill_pos -= 1
j -= 1

```

I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

/

## Wave sort

Question 43. Re-arrange the elements in an array like a wave so that the values of the array alternately increase and decrease. The elements in the array are unique. For instance, if A = {50, 10, 20, 30, 40}, after re-arranging A can be {10, 30, 20, 50, 40} where in the value of consecutive elements alternately increases and decreases

This problem can be solved in O(nlogn) without additional memory as follows:

1. First sort the entire array in ascending order. So {50, 10, 20, 30, 40} becomes {10, 20, 30, 40, 50}

2. Then starting from index 1 in the array, swap the neighboring elements. So {10, 20, 30, 40, 50} becomes {10, 30, 20, 50, 40}

## C/C++

```
/*
a: array that has to be sorted so that the values in it alternatively increase
and decrease. The elements should be unique
length: number of elements in the array. should be >= 1
*/
void wave_sort(int a[], int length)
{
int i, temp;

/*Sort the elements in ascending order*/
qsort(a, length, sizeof(int), cmp_function);

/*Swap the alternate elements*/
for (i = 1; i < length - 1; i += 2) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}

```

## Java

```
/*
a: non-empty array that has to be sorted so that the values in it
alternatively increase and decrease. The elements should be unique
*/
public static void waveSort(int[] a) {
/*Sort the elements in ascending order*/
Arrays.sort(a);

/*Swap the alternate elements*/
for (int i = 1; i < a.length - 1; i += 2) {
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}

```

## Python

```
#a: non-empty list that has to be sorted so that the values in it
#	alternatively increase and decrease. The elements should be unique
def wave_sort(a) :
#Sort the elements in ascending order
a.sort()

#Swap the neighboring elements
for  i in range(1, len(a) - 1, 2):
a[i], a[i+1] = a[i+1], a[i]

```

I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

/