I ran across this puzzle about 10 years ago. Although it didn’t take me long to come up with the optimum solution, I find the puzzle interesting because it just might be a good interview question for programmers at different levels of experience.

The puzzle:

Given an unsorted array of distinct integers, arrange them such that a1 < a2 > a3 < a4 > a5 < a6 ... So, for example, given the array [9,6,3,1,4,8], one valid arrangement would be [6,9,1,8,3,4]

The obvious solution is to sort the numbers and then interleave them. Put the smallest number at a1, the largest at a2, second smallest at a3, etc. Sorted, our sample array is [1,3,4,6,8,9]. If we interleave the numbers as I describe, the result is [1,9,3,8,4,6]. It’s easy enough to check if that’s right: just replace the commas with alternating < and >: [1<9>3<8>4<6].

Any programmer fresh out of school should be able to come up with that solution and code it, and tell me that the complexity is O(n log n) because of the sort. If a junior programmer supplied that solution to the problem, I’d be satisfied.

But there is an O(n) solution that I’d expect an intermediate or senior engineer to discover if prompted. That is, if they told me the solution was to sort and interleave, I’d ask them if they could think of a solution with lower expected running time.

Given any three successive numbers in the array, there are four possible relationships:

1. a < b < c
2. a < b > c
3. a > b < c
4. a > b > c

The relationship we desire is (2).

In case (1), the first condition is already met (a < b), and we can swap b and c to give us a < c > b.

In case (2) both conditions are met so we don’t have to do anything.

In case (3), we swap a and b to give us b < a ? c. But we already know that b < c, so if we have to swap a and c to meet the second condition, the first condition is still met.

In case (4), we know that a > c, so if we swap a and b to meet the first condition, the second condition is still met.

Now, add a fourth number to the sequence. You have a < b > c ? d. If it turns out that c < d then there’s nothing to do. If c > d then we have to swap them. But that doesn’t mess up the previous condition because if b > c > d then by definition b > d.

You use similar logic to add the fifth number. You have a < b > c < d ? e. If d > e then there’s nothing to do. If d < e then by definition c < e, so swapping d and e doesn’t invalidate anything that comes before.

That understanding leads to this pseudocode that makes a single pass through the array, swapping adjacent values as required:

for i = 0 to n-2
    if i is even
        if (a[i] > a[i+1])
            swap(a[i], a[i+1])
        end if
    else // i is odd
        if (a[i] < a[i+1])
            swap(a[i], a[i+1])
    end

I find that very elegant.