Monthly Archives: November 2013

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.

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.

Merge two sorted linked lists

Given two sorted linked lists, how do we merge them without using any extra space. That means we have to re-arrange the links to form a single sorted linked list.
For example let us consider the following two sorted lists as input.
1 -> 3 -> 5 -> 7
2 -> 4 -> 6 -> 8
The output should be
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
The algorithm is simple. We take the smaller node between the two lists in each iteration, and add it to the result list. We do this until we process any of the list to completion. If there is any remaining portion of the other list, we join it with the result list.
Here is the C++ code do this.
  

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.

Level order traversal of a binary tree

Given a binary tree, we have to print the data level wise. 
For example level order traversal of the following tree produces the sequence 5,3,8,2,4,6,1,7.
The hint to solve this problem is to use a Queue data structure. We start by inserting the root node into the queue. Until the queue is empty, we remove the first element from the queue and insert it’s left and right children at the last.

This will give us the level order traversal of the binary tree. For example look at the queue state at each iteration.
5
3,8
8,2,4
2,4,6
4,6,1
Here is the C++ program which contains the level order traversal function.

Finding the minimum and maximum elements in a binary seach tree

Given a binary search tree, how do we find the maximum and minimum elements in it?

For example in the given tree, the maximum element is 8 and the minimum element is 1.
This algorithm is based on the following simple observation.
In a Binary search tree, the minimum element always lies on the left most node and the maximum element always lies on the right most node.
Here is the simple implementation of this algorithm in C++.