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

Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

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

WRONG ANSWER!

public class Solution {
    public void wiggleSort(int[] nums) {
        int cur=0, next=cur+1;
        int id=0;
        boolean look4large = true;
        while(cur<nums.length-1){
            if(nums[next]==nums[cur]){
                while(nums[next]==nums[cur]) next++;
            } 
            if((look4large && nums[next]>nums[cur])
                        || (!look4large && nums[next]<nums[cur])){
                id = cur+1;          
            } else {
                id = cur;
            }
            if(id!=next){
                int tmp = nums[next];
                nums[next] = nums[id];
                nums[id] = tmp;
            }
            cur++;
            next = cur+1;
            look4large = look4large ? false : true;
        }
    }
}

Runtime Error Message:

Line 8: java.lang.ArrayIndexOutOfBoundsException: 4
Last executed input:
[4,5,5,6]

CORRECT SOLUTION

Solution:

public class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int mid = findKthLargest(nums, n/2);
        int i = 0, lo=0, hi=n-1;
        while(i<=hi){
            if(nums[map(i, n)]>mid){
                swap(nums, map(i, n), map(lo, n));
                i++;
                lo++;
            } else if(nums[map(i, n)]<mid){
                swap(nums, map(i, n), map(hi, n));
                hi--;
            } else {
                i++;
            }
        }
    }
    public int findKthLargest(int[] nums, int k) {
        int lo=0, hi=nums.length-1;
        int pos = -1;
        while(lo<=hi){
            pos = partition(nums, lo, hi);
            if(pos<nums.length-k){
                lo = pos + 1;
            } else if(pos>nums.length-k){
                hi = pos - 1;
            } else {
                break;
            }
        }
        return nums[pos];
    }
    public int partition(int[] nums, int low, int high){
        if(low==high) return low;
        int pivot=nums[low];
        int lo=low+1, hi=high;
        while(lo<=hi){
            while(lo<=hi && nums[lo]<=pivot) lo++;
            while(lo<=hi && nums[hi]>pivot) hi--;
            if(lo<hi) swap(nums, lo, hi);
        }
        swap(nums, low, hi);
        return hi;
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;
    }
    public int map(int i, int n){
        return (1+2*i)%(n|1);
    }
}