Sort an Array in Wave Form

Given an unsorted array of integers (duplicates allowed), rearrange it into wave form:

Text

a[0] >= a[1] <= a[2] >= a[3] <= a[4] ...

If there are several wave arrangements, return the lexicographically smallest one.

Example

Text

Input:  [5, 2, 9, 3, 2]       Output: [2, 2, 5, 3, 9]
Input:  [3, 2, 9, 6, 4, 1]    Output: [2, 1, 4, 3, 9, 6]

Sort, then swap neighbours

After sorting, a[0] <= a[1] <= a[2] .... Swapping each pair (0, 1), (2, 3), ... puts the larger value of every pair first. Each pair's larger value is also no larger than the next pair's smaller value, so both conditions hold. The result is the smallest wave possible: position 0 gets the second-smallest value (the smallest can't go first unless it's tied), position 1 the smallest, and so on.

Java

import java.util.Arrays;

public class Main {
    static void wave(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i + 1 < nums.length; i += 2) {
            int tmp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[][] inputs = {{5, 2, 9, 3, 2}, {3, 2, 9, 6, 4, 1}};
        for (int[] nums : inputs) {
            wave(nums);
            System.out.println(Arrays.toString(nums));
        }
    }
}

Output

[2, 2, 5, 3, 9]
[2, 1, 4, 3, 9, 6]

Time: O(n log n). Space: O(1) extra (Arrays.sort on an int[] sorts in place).

The loop condition i + 1 < nums.length stops before a final unpaired element, which can stay where it is.

O(n) when any wave will do

If the lexicographic requirement is dropped, sorting isn't needed. Visit the even indices only. Each should be at least as large as both neighbours, so swap it with any neighbour that is larger. Swapping with the left neighbour can't break the pair before it, because that neighbour (an odd index) only gets larger values than it had.

Java

import java.util.Arrays;

public class Main {
    static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    static void wave(int[] nums) {
        for (int i = 0; i < nums.length; i += 2) {
            if (i > 0 && nums[i - 1] > nums[i]) swap(nums, i - 1, i);
            if (i + 1 < nums.length && nums[i + 1] > nums[i]) swap(nums, i, i + 1);
        }
    }

    static boolean isWave(int[] nums) {
        for (int i = 0; i + 1 < nums.length; i++) {
            boolean ok = i % 2 == 0 ? nums[i] >= nums[i + 1] : nums[i] <= nums[i + 1];
            if (!ok) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] inputs = {{5, 2, 9, 3, 2}, {3, 2, 9, 6, 4, 1}};
        for (int[] nums : inputs) {
            wave(nums);
            System.out.println(Arrays.toString(nums) + " " + isWave(nums));
        }
    }
}

Output

[5, 2, 9, 2, 3] true
[3, 2, 9, 4, 6, 1] true

Time: O(n). Space: O(1).

Edge cases

Duplicates: >= and <= allow equal neighbours, so [2, 2] is already a wave.
Fewer than two elements: already a wave.