Wiggle Sort — Leetcode problem 280

Original problem link: https://leetcode.com/problems/wiggle-sort/

In this problem, we’re asked to reorder an array of numbers such that nums[0] <= nums[1] >= nums[2] <= nums[3]…etc.

My most efficient implementation is as follows (O(n)):

class Solution {
    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (i % 2 == 1 && nums[i] < nums[i - 1]) {
                int temp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = temp;
            }
            if (i % 2 == 0 && nums[i] > nums[i - 1]) {
                int temp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = temp;
            }
        }
    }
}

In essence, we check whether the current num should be larger or smaller than the one before it based on whether the index is odd or even, and swap if it is in the wrong order.

My initial thought was to sort it and swap each pair, but that is slightly slower (3–4 ms vs 1 ms for the efficient solution), since sorting is O(nlogn) at the minimum.

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length - 1; i+=2) {
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
    }
}