Sunday, June 23, 2013

Unsorted Array Converted To "E1 < E2 > E3 < E4..." Format

I had a question once where given an unsorted array of integers, you have to produce an array in the "E1 < E2 > E3 < E4..." format. For example {3, 2, 6, 4, 9, 7, 1, 10, 8, 5} would produce {2, 6, 3, 9, 4, 7, 1, 10, 5, 8} and this is because 2 < 6 > 3 < 9 > 4 < 7 > 1 < 10 > 5 < 8.

This is a tricky question where if asked by an interviewer you have to ask follow-up questions! I'm saying this out of my experience, my first solutions that I had in mind when I first had this question asked were involving sorting or priority queues, thus at least O(n log n) running time and involving additional space. But when I asked about the desired running time I was told that it should be faster, so I revisited my thoughts. It is in fact a very simple problem where you have to traverse the array just once resulting in O(n) running time. Note that you also have to ask about how to handle duplicates, in this case I considered an array of unique numbers.

The idea is that while traversing the array, you maintain a flag that indicates whether a "less than" or a "greater than" comparison should succeed. If it does not succeed you swap the previous index with the current index.

This will be easier to understand through an example. Let's say we have the above array {3, 2, 6, 4, 9, 7, 1, 10, 8, 5}. We traverse the array starting at the second element (2), since we'll be comparing the current with the previous element. We also have to maintain the above mentioned flag, say a flag named lessThan which will be defaulted to true since our format definition indicates that we have to start from a less than sign. So we have our element "2" and previous element "3". Is element "3" less than element "2" ? No, then we swap the elements which results in the array {2, 3, 6, 4, 9, 7, 1, 10, 8, 5}. We also have to switch the lessThan flag and then go to the next index. Now the flag tells us that we have to use the "greater than" sign. Is element "3" greater than element "6" ? No, then swap the numbers. But wait, what happens to the previous comparison ? The second index has to stay greater than the first one, but note that this did get verified by the condition that we just imposed by comparing "6" with "3". "6" is greater than "3", which is greater than "2" - this means "6" is greater than "2", thus it's safe swapping "6" with "3". This results in {2, 6, 3, 4, 9, 7, 1, 10, 8, 5}. This goes on until the end of the array. Here's a table that may add more sense to how the algorithm works:

Iteration Array LessThan flag Swapped
0 2, 3, 6, 4, 9, 7, 1, 10, 8, 5 true true
1 2, 6, 3, 4, 9, 7, 1, 10, 8, 5 false true
2 2, 6, 3, 4, 9, 7, 1, 10, 8, 5 true false
3 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 false true
4 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 true false
5 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 false false
6 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 true false
6 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 false false
7 2, 6, 3, 9, 4, 7, 1, 10, 5, 8 true true

The code is pretty simple. See it below:
Note:
- The swap function is trivial and it may look like in the code below.