# Java Solution with Explanation & Thoughts

• The basic idea is to make sure that every odd position is greater than (or equal to) its two adjacent even postions. For example, if the current odd position is `i`, then we need to make sure the `nums[i-1] <= nums[i]` and `nums[i+1] <= nums[i]`. If you do that for the entire array, then the result will satisfy Wiggle Sort's requirement. (It's kind of like a greedy solution IMO, where local optimum leads to global optimum).

I also thought about the proof (please tell me if i'm wrong here). I was wondering if there could be a case where a group of 3 numbers couldn't be arranged to meet the requirement. Turns out this is not the case. Let's say we have 3 consecutive numbers in the mid of the array `a, b, and c`, where `b` is at an odd index and `a, c` are at even indices. There are only 4 possible cases:
`1. a <= b <= c --> swap(b, c)`
`2. a <= b >= c --> done`
`3. a >= b <= c --> swap(a, b), then it could be either case 1 or 2`
`4. a >= b >= c --> swap(a, b)`
Whatever the case it is, we will always be able to satisfy the requirement `nums[i-1] <= nums[i]` and `nums[i] >= nums[i+1]`. In addition, whether we swap `(a, b)` or not, it will still maintain the correct order for the previous group (e.g. if we have `d, a, b, c` where `d >= a`. If `a >= b` then we `swap(a, b)`, but still `d >= b`). Thus, if we do this operation to each `[even, odd, even]` index group of the array, then we should have the final solution.

My code can be more concise, but I want it to be crystal clear so I wrote it in the more verbose way.

``````public class Solution {
public void wiggleSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if (i % 2 == 0 && nums[i-1] < nums[i]) {  // at even index, check if it's greater than previous number
swap(nums, i-1, i);
}
if (i % 2 != 0 && nums[i-1] > nums[i]) {  // at odd index, check if it's smaller than previous number
swap(nums, i-1, i);
}
}
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
``````

• what if it's consecutive same numbers, let's assume:

• @vincent.zou Notice this is wiggle sort 1 not 2: `nums[0] <= nums[1] >= nums[2] <= nums[3]`

[1,1,1,1,1,2,2,2,2,2]
when input
[1,1,1,1,1,2,2,2,2,2].

because nums[i-1] == nums[i], and you simply do nothing in your code right?

• @vincent.zou The input you given is already an acceptable result.

• @yuhao5 Nice solution!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.