Wiggle Sort

Share

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

There may have multiple answers for a question, you only need to consider one of the possibilities.

Example 1
Input: nums = [3, 5, 2, 1, 6, 4]
Output: [1, 6, 2, 5, 3, 4]
Explanation: This question may have multiple answers, and [2, 6, 1, 5, 3, 4] is also ok.
Example 2
Input: nums = [1, 2, 3, 4]
Output: [1, 4, 2, 3]

Contents

Solution 1 - Swap elements at even and odd positions if conditions dont match

As per the problem statement, re-ordering of elements should be done in-order, i.e without using additional memory. One way we can do that is by sorting the input array first using Arrays.sort(nums), by doing so odd position elements already positioned correctly with given condition, then for all elements at even index i =1 and above, swap elements with i-1 index.
For example, consider input array as nums = [3, 5, 2, 1, 6, 4], after sorting it will become [1, 2, 3, 4, 5, 6] and if we swap even indexed elements with i-1 for all elements i =1 and above, then the resultant array will be [1, 3, 2, 5, 4, 6], which is one of the possible answer that matches the wiggle sort conditions.

Above, algoritm will take O (n log n) to sort the numbers. But, we can do it better using below approach, for every index i =1 or above:

  • If it is an even index, we will compare with i+1th indexed element, if the value at i+1th index is greater than value at ith index, then we will swap them.
  • If it is an even index, we will compare with i-1th indexed element, if the value at ith index is less than value at i-1th index, then we will swap them.

Java
import java.util.Arrays;

public class WiggleSort {

    static void wiggleSort(int[] nums) {

        if(nums.length == 1) {
            return;
        }
        int i=1;
        while(i <nums.length) {
            if(i%2 == 1&& nums[i] <nums[i-1]) {
                swap(nums, i, i-1);
            }
            if(i%2 == 0 && i+1 < nums.length && nums[i+1] > nums[i]) {
                swap(nums, i, i+1);
            }
            i++;
        }
    }

    static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

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

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(1), since we are swapping elements in-place.

Above implementations source code can be found at GitHub link for Java code