# 324. Wiggle Sort II (Medium)

https://leetcode.com/problems/wiggle-sort-ii/

Given an unsorted array `nums`, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]...`.

Example 1:

```Input: `nums = [1, 5, 1, 1, 6, 4]`
Output: One possible answer is `[1, 4, 1, 5, 1, 6]`.```

Example 2:

```Input: `nums = [1, 3, 2, 2, 3, 1]`
Output: One possible answer is `[2, 3, 1, 3, 1, 2]`.```

Note:
You may assume all input has valid answer.

Can you do it in O(n) time and/or in-place with O(1) extra space?

## Solutions

``````class Solution {

// This problem is too complicated, do not try again

public void wiggleSort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}

int len = nums.length;

// tmp is a temporary memory used to scan out the medium
int[] tmp = new int[len];

System.arraycopy(nums, 0, tmp, 0, nums.length);

// Sort out the medium by which the nums is divided into two relatively equal size
// parts and the elements in left section is smaller than that in right section.
int medium = partition(tmp, 0, len - 1, len / 2);

int[] ans = new int[len];

// This is critical
Arrays.fill(ans, medium);

// stands for even index slot
int evenPtr = 0;

// stands for odd index slot
int oddPtr = 1;

for (int i = 0; i < len; i++) {
// every even index swap in a smaller element in the left section.
if (nums[i] < medium) {
ans[evenPtr] = nums[i];
evenPtr += 2;
}
// every odd index swap in a larger element in the left section.
else if (nums[i] > medium) {
ans[oddPtr] = nums[i];
oddPtr += 2;
}
}

System.arraycopy(ans, 0, nums, 0, nums.length);
}

private int partition(int[] nums, int l, int r, int mid) {
int left = l;
int right = r;

int midVal = nums[left];

// Sort nums by descending order.
// Only left == right it will jumps out of the loop
while (left < right) {

// if left >= right is the cause to jump out the loop, left = right
while (left < right && nums[right] >= midVal) {
right--;
}

nums[left] = nums[right];

// if left >= right is the cause to jump out the loop, left = right
while (left < right && nums[left] <= midVal) {
left++;
}

nums[right] = nums[left];
}

if (left ==  mid) {
return midVal;
}

if (left <  mid) {
return partition(nums, left + 1, r,  mid);
}

// left > mid
return partition(nums, l, right - 1,  mid);
}
}
``````