280. Wiggle Sort

/**

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

 * nums[3]….

 *

 * Example:

 *

 * Input: nums = [3,5,2,1,6,4] Output: One possible answer is [3,5,1,6,2,4]

 */

See the code at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/WiggleSort.java

Observation: The question is asking to sort the numbers by the below conditions:

1. Alternatively ensure each of the below
   1. Val[index] <= Val[index+1]
   1. Val[index] >= Val[index+1]
      
      

So, we can simply iterate from left to right and ensure that the above conditions are being held. Logic is extremely straightforward. The only quirk is that mentally we map sort with merge sort, quick sort, etc. The above conditions don’t translate into any of the regular sort operations so need to ensure we don’t get confused….

Here is the code:

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