# Use partition algorithm. Easy to understand. O(n) time O(n) space.

• ``````public class Solution {
public int partition(int[] arr, int beg, int end) {
int pivot = arr[beg];
end++;
while (beg < end) {
while (beg < end && arr[--end] > pivot);
arr[beg] = arr[end];
while (beg < end && arr[++beg] <= pivot);
arr[end] = arr[beg];
}
arr[beg] = pivot;
return beg;
}

private void swap(int[] arr, int a, int b) {
int t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}

public void wiggleSort(int[] nums) {
int n = nums.length;
int k = n / 2 - 1;
if (n % 2 == 1) k++;
int beg = 0, end = n-1;
for (;;) {
int t = partition(nums, beg, end);
if (t == k) {
if (k+1 < n && nums[k] == nums[k+1]) {
int val = nums[k];
for (int j = 0, i = 0; j <= k; j++) {
if (nums[j] == val) swap(nums, j, i++);
}
for (int j = n-1, i = n-1; j >= k+1; j--) {
if (nums[j] == val) swap(nums, j, i--);
}
}
break;
} else if (t < k) {
beg = t+1;
} else if (t > k) {
end = t-1;
}
}
int[] arr = nums.clone();
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
nums[i] = arr[i/2];
} else {
nums[i] = arr[i/2+k+1];
}
}
}
}
``````

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