Lexicographically smallest wave like array without sorting

Question

Given an array of integers, sort the array into a wave like array and return it. In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....

Example:

Given [1, 2, 3, 4]

One possible answer: [2, 1, 4, 3]

Another possible answer: [4, 1, 3, 2]

NOTE: If there are multiple answers possible, return the one that's lexicographically smallest. So, in example case, you will return [2, 1, 4, 3].

My solution is \$O(n\log n)\$ time since they want lexicographically. I'm unable to come up with a linear time solution for lexicographically smallest case. My questions here is, is it even possible to do that in \$O(n)\$ without sorting? I looked up online quite a bit and don't see any linear time solution for this scenario.

  public ArrayList<Integer> wave(ArrayList<Integer> a) {
    Collections.sort(a);
    if(a.size() == 0 || a.size() == 1)
        return a;
    int temp = -1;
    for(int i = 1; i < a.size(); i++) {
        if(i%2 == 0 && a.get(i) < a.get(i-1)) {
            temp = a.get(i);
            a.set(i, a.get(i-1));
            a.set(i-1, temp);
        }
        if(i%2 == 1 && a.get(i) > a.get(i-1)) {
            temp = a.get(i);
            a.set(i, a.get(i-1));
            a.set(i-1, temp);
        }
    }
    return a;
  }

Answer 1

I don't think this could be done without sorting, but there are a couple of aspects that can be improved with the current code. First of all, there is code duplication; the part

temp = a.get(i);
a.set(i, a.get(i-1));
a.set(i-1, temp);

is duplicated between the two branches of the code. A first step would be to suppress that duplication. There are several approaches, like merging the two if statements in a single one with

if (i%2 == 0 && a.get(i) < a.get(i-1) || i%2 == 1 && a.get(i) > a.get(i-1))

but it becomes a bit unclear. Another approach would be to factor that into a swap method, that swaps two indexes of a list... and you actually don't need to write one, because it already exists! You can just have:

Collections.swap(a, i, i - 1);

without having your own temporary variable.

But there is an even simpler approach: since the list was sorted in ascending order before hand, the result can be found directly by swapping the items two by two. It makes sure that the result is the smallest lexicographically (thanks to the sort) and that each item verify the condition (thanks to the swap). So instead of having an index i going over the number and increasing by 1, have it increase by 2 and always swap i with i + 1.

for (int i = 0; i < a.size() - 1; i += 2) {
    Collections.swap(a, i, i + 1);
}

This takes care of 2 problems at once:

• There is no need for any if checks with regard to the parity of i: by construction of the loop, it will always be even, so the loop will swap an element with the element after it, and then go to the next unswapped element.
• It also fixed the duplication issue.

Note that the loop needs to go to a.size() - 1 because we're increasing by steps of 2, and an odd number of elements shouldn't cause problems.

if (a.size() == 0 || a.size() == 1)
  return a;

Instead of checking if the size is 0, use isEmpty() which is cleaner. But actually, you don't need those early-returns to begin with, since the rest of the code handles them fine without any overhead (the for loop won't be executed, and the method will return directly). You can safely remove them.

public ArrayList<Integer> wave(ArrayList<Integer> a)

You should make the methods as generic as they can be:

• Don't code against ArrayList. What if the user wants to pass another type of list? For example, consider the following:

  wave(Arrays.asList(1, 2, 3, 4, 5))
  

  This won't compile because the given list is not an ArrayList. This should be perfectly safe to do, even though asList returns a fixed-size list, the method is not going to add or remove elements from it, just sort and swap values. Therefore, switch to using the general List:

  public List<Integer> wave(List<Integer> a)
  

• That also forces the user to want to wave only lists of integers. What if they want to sort longs?

  public <T extends Comparable<? super T>> List<T> wave(List<T> a)
  

  would enable that use-case. The elements have to be comparable so that the constraint "a1 >= a2 <= a3 >= a4 <= a5" is possible, so adding extends Comparable makes sense.

• The method actually modifies in-place the given list. It does not return a new list, but updates the given list. I would make the method not return the updated list as well. If the method returns something, the user probably expects it to return a new object, not to modify the given argument. Therefore, when the method does modify its argument in-place, don't return it; it makes it clear that the method is doing this in-place modification. The JDK utility methods do this as well (for example in the Collections or Arrays classed).