Merging two sorted arrays

Given two sorted arrays A, B of lengths m, n respectively. How to merge them into a single sorted array?. Let us assume that A has sufficient space (m+n) for result array.
For example let A = [1, 3, 5, 7, 9], and B = [2, 4, 6, 8, 10]. The function should return A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] as a result.

Since the array A has sufficient space for the merged array, we can start from the end of the array A and start filling the result elements.

We compare the elements at i and j indices. We move the bigger element to the end pointed by res and decrement the corresponding index. We do this until we reach the beginning of any array. Finally we check if there any left over elements in the second array. If there are, we have to move them to the first array.

Minimum difference between two sorted arrays

Given two arrays sorted in ascending order, find the absolute minimum difference between any pair of elements |a-b| such that a is from one array and b is from another array.

For example consider the following two arrays.

array1 = [3, 27, 45, 68, 70, 81, 99]
array2 = [9, 16, 25, 35, 70, 84]
The minimum difference is 2 (27-25).
This can be calculated using the following algorithm.
1. Take two indices i, j which point to the beginning of the two arrays (i.e 0)
2. Take variable MinDiff and assign it the maximum possible value
3. If array1[i] and array2[j] are equal return 0
4. Otherwise update MinDiff if abs( array1[i] – array2[j] ) is the new minimum.
5. If array1[i] > array2[j] move second index(j) forward otherwise move first index (i) forward.
6. Repeat the above procedure until we reach the end of any of the two arrays.
7. Finally process the remaining part of left-over array to update MinDiff

This algorithm takes linear time – O(n) and constant space O(1). Here is the Java implementation of the above algorithm.

Finding the kth smallest element in the array

Given an array of numbers, how do we efficiently find the Kth smallest number in it?

This problem is also called the selection problem. Widely used in order statistic (Find the smallest, biggest, median, top K elements etc…)

For example in the array [6, 1, 9, 8, 3, 5, 4] the third smallest element is 4.
An obvious approach could be to sort the entire array and return the element array[K-1]. But this approach takes O(n log n) time in the worst case (Sorting time).
Another simple approach could be to perform first K steps in either insertion sort or selection sort which gives us the required element. But this approach takes time proportional to K.
Can we do better than this?
We can use the partition method used in Quick sort to solve this problem. The partition method divides the array into two parts based on a pivot element. The pivot element is in it’s correct position. All the elements to the left of it are less than or equal to pivot, and all the elements to the right of it are greater than pivot. Finally it returns the pivot position.
We can compare the pivot with K. If it is equal  we are done!. If pivot is less than K, we need to search the right-side partition otherwise we need to search the left side partition.
Here is the Java implementation of the above algorithm.

Finding two numbers occuring once

Given an array containing all elements twice except two numbers. Write a program to find those two numbers.
For example let us consider the following array
{2, 3, 2, 1, 4, 1, 4, 5}
The answer is {3,5} because they appear only once and all remaining elements appear twice.
This question is somewhat similar to earlier post. This gives us a hint to use XOR operation to solve this problem. Let us see how we can utilize XOR operation.
We first find the XOR of all the elements in the array. This gives a bit pattern which is an XOR of required two values because all other elements occurs twice they get zeroed out.

For the above example the xor value is 0110 = 0011 ^ 0101

Let the two unique numbers are x, y. The next problem is how to find x,y from this xor value. Let us denote ith bit is the first set bit in the xor result. We divide all the numbers in the array into two parts. One part containing all the numbers with bit i = 1, and the other part containing all the numbers with bit i = 0;

This partition segregates the numbers such that all the pairs with ith bit 1 goes to one partition and all pairs with ith bit 0. But x and y fall into two different buckets their bit patterns will be different.

Now finding the XOR value of these partitions separately gives us the required result.

In the above example. The XOR value has 1st bit as 1.
{2,2,3} forms one partition and {1,1,4,4,5} forms another partition.

Parition-1    Partion-2
0010          0001
0011          0100
0010          0001
0100
0101
———————
0011(3)     0101(5)

Here is the Java code to do this.

Printing the matrix in a spiral order

Given a two dimensional array or a matrix, how do we write a program to print the elements in a spiral order.
For example the spiral order for the following matrix is
1  2  3  4  8  12  16  15  14  13  9  5  6  7  11  10
1   2   3   4
5   6   7   8
9  10  11  12
13 14  15  16

The algorithm for this problem involves four steps.

• Print the elements of the top row from left to right and increment top.
• Print the elements of right column from top to bottom and decrement right.
• Print the elements of bottom tow from right to left and decrement bottom.
• Print the elements of left column from bottom to top and increment left.

Repeat the above steps until there are no more elements left.

As the algorithm indicates, we need four variables to keep track of the top and bottom rows, left and right columns. We also use an extra variable for the direction. It can have four values indicating four possible directions.

Here is the Java implementation of the above algorithm.

Given a doubly linked list, how do we reverse it by just re-arranging the pointers?
Here is an example of input/output.
The following picture depicts how we re-arrange the pointers.

Here is the Java implementation.

Checking if any anagram of a given string is palindrome or not

Given a string, how do we check if any anagram of it can be a palindrome?
For example let us consider the string “AAC”. An anagram of it is “ACA” which is a palindrome. We have to write a method which takes a string and outputs true if we can form a palindrome from any anagram of the given string. Otherwise outputs false.
We can immediately think of a solution where we can generate all anagrams of the given string and check if there is any palindrome exists. But this approach is very lengthy and has exponential time complexity (O(n!)).
The key to solve this problem efficiently is to understand how a palindrome is formed. We all know that a palindrome reads the same when you read from left to right or right to left.

A palindrome can be broken into two halves. where in the first half is the reverse of second half. In case of odd length of strings, we have to ignore the middle character.

So for every character in the first half, there is a corresponding matching character in the second half. This indicates that all the characters in a string must occur even number of times except for one which appears in the middle of the string.

Hence if we check if there is at most one character with odd occurrences in the string we can say that we can form a palindrome from any anagram.

Here is the Java code which implements this algorithm. For simplicity, I assumed that the input string contains only lowercase English alphabets.

Merging k sorted lists

Given K sorted lists, how to merge them into a single sorted list?
Let total number of elements in K sorted lists is N. We have to form a single sorted list of length N.

For example let us consider the following input lists
{4, 19, 27}
{1, 6, 50, 73}
{9, 45, 59, 67}

The output should be {1, 4, 6, 9, 19, 27, 45, 50, 59, 67, 73}.

In this post, we discuss an efficient approach by using priority queues (heaps). This problem is one of the nice examples of using priority queues.

Here is how the algorithm works.
1. Add the first elements from all the lists into a priority queue along with their list indices.
2. Until the priority queue is empty, do the following
1. Remove the minimum element from the priority queue and add it to the result list. Let this minimum element belongs to min_list.
2. Add the next element from min_list to the priority queue if there exists at least one element.

Here is the Java implementation of the above algorithm.

Time complexity of this algorithm is O(N log K) as we have N elements in total, and insert and remove-min operation of the priority queue takes O(log k) time.

Finding three elements with zero sum in an array.

Given an array of positive and negative numbers, how do we write a program to check if it has three elements with sum 0.

For example, the array  {-31, 19, -6, -45, 12, -8, 3, -77, 56, 29} contains {-31,12,19} with sum zero.

One obvious solution is to examine each possible triplet of the array and check if there is a triplet with sum = 0. But this takes O(n3) time and is not efficient for large arrays.

A better approach would be to sort the array first in increasing order. Follow this iterative algorithm.

• Fix the first element, start two pointers one at the begin and the other at the end of the sorted array.
• If the sum of the three elements is zero return.
• If the sum is greater than zero, we decrement the end pointer so that the sum moves closer to zero
• If the sum is negative, we increment the begin pointer to add up value to sum.
• Iterate this procedure until the fixed element moves towards the end.

This procedure takes O(n log n) for sorting the array and O(n2) for actually finding the triplet. So the overall time complexity would be O(n2) and O(1) extra space.

Here is the java code to do this.

Searching for an element in the sorted matrix

Given a row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently?

Example of the array can be

int[][] matrix = {
{1,3,5,7,9},
{10,12,14,16,18},
{19,21,23,25,27},
{28,30,32,34,36},
{37,39,41,43,45}
};

This can be done using the following algorithm.

We start our search with the top right element.

• If it is equal to the key, we print corresponding indices and we are done!.
• If the key is greater than the current element, we move to the next row because all the elements in the current row prior to this element are lesser.
• If the key is less than the given element, we move to the previous column.  The reason is similar to the above.

We continue this search until we find the key or until we confirm the element is not present. If we reach last row first column, we can confirm that the element is not present.

Here is the java implementation of the above algorithm. The time complexity of this program is O(n) and n is the number of rows and columns.