Leetcode: Wiggle Sort II

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?

Understand the problem:
The mainly difference between Wiggle sort I and II is this question asks for nums[even] < nums[odd], not nums[even] <= nums[odd]. So If we still use the greedy solution, it may not find out a valid solution. 

An O(nlogn) time solution, out-of-place:
We can first sort the array, then partition the array into two halves. So all elements in the first half is less than the second half. Then we can pick up one element from each half from the end, and form the solution . e.g. 
nums = [1, 3, 2, 2, 3, 1]. 

After the sorting, the array becomes [1, 1, 2, 2, 3, 3]. Then we partition the array into two halves, the left half is [1, 1, 2]. The right half is [2, 3, 3]. Then we pick up one element from each and form the solution.
[1, 1, 2]            [2, 3, 3]
         |                        |
       left                    right
2, 3, 1, 3, 1, 2

Since there must be a solution, the left element we choose each time must be less than the right element (why ? because if the left is equal to the right, all elements before right and after left must be equal as well, so there will be no solution existed). 

Note that if there are odd number of elements, the left half must be 1 more than the right, not reverse. That is because the last element must be indexed as even (e.g. 0, 1, 2, 3, 4, 5, 6), and since nums[even] < nums[odd], so the last number must be in the smaller half. 


Code (Java):

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        Arrays.sort(nums);
        int n = nums.length;
        
        int[] temp = new int[n];
        int left = (n - 1) / 2;
        int right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                temp[i] = nums[left];
                left--;
            } else {
                temp[i] = nums[right];
                right--;
            }
        }
        
        System.arraycopy(temp, 0, nums, 0, n);
    }
}

A wrong solution:

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        Arrays.sort(nums);
        int n = nums.length;
        
        int[] temp = new int[n];
        int left = 0;
        int right = (n + 1) / 2;
        
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                temp[i] = nums[left];
                left++;
            } else {
                temp[i] = nums[right];
                right++;
            }
        }
        
        System.arraycopy(temp, 0, nums, 0, n);
    }
}

Why the solution is wrong?

Input:[4,5,5,6]

Output:[4,5,5,6]

That is mainly because although the 4 must be less than 5 for the first two elements in the result, there is no guarantee that the third element must be less than the second element.  

A O(n) time, out-of-place solution:
We can use a quick select algorithm to find out the median of the array, so the first half is less than the second half. 

Note that we must do a 3-way partition before doing the wiggle sort. That is, we need to put all elements less than the median into the left, all median elements in the middle, and all element greater than the median into the right. This can guarantee that  while each time we pick up an element on the left and right half, they are absolutely not equal. 

Code (Java):

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        int n = nums.length;
        
        // Step 1: Find median of the array, return the index of the median
        int median = findMedian(nums, 0, n - 1, (n - 1) / 2);
        
        // Step 2: 3-way sort, put median in the middle, 
        // numbers less than median on the left, 
        // numbers greater than median on the right
        int[] temp = new int[n];
        int left = 0;
        int right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[median]) {
                temp[left] = nums[i];
                left++;
            } else if (nums[i] > nums[median]) {
                temp[right] = nums[i];
                right--;
            }
        }
        
        // add median into the middle
        for (int i = left; i <= right; i++) {
            temp[i] = nums[median];
        }
        
        // Step 3: wiggle sort
        left = (n - 1) / 2;
        right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                nums[i] = temp[left];
                left--;
            } else {
                nums[i] = temp[right];
                right--;
            }
        }
    }
    
    private int findMedian(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return lo;
        }
        
        int pivot = partition(nums, lo, hi);
        if (pivot == k) {
            return pivot;
        }
        
        if (pivot > k) {
            return findMedian(nums, lo, pivot - 1, k);
        } else {
            return findMedian(nums, pivot + 1, hi, k);
        }
    }
    
    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int i = lo + 1;
        int j = hi;
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] >= pivot) {
                j--;
            }
            
            if (i <= j) {
                swap(nums, i, j);
            }
        }
        
        swap(nums, lo, j);
        
        return j;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Alternative solution using in-place 3-way partition:

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        int n = nums.length;
        
        // Step 1: Find median of the array, return the index of the median
        int median = findMedian(nums, 0, n - 1, (n - 1) / 2);
        
        // Step 2: 3-way partition, put median in the middle, 
        // numbers less than median on the left, 
        // numbers greater than median on the right
        int left = 0;
        int right = n - 1;
        int j = 0;
        while (j <= right) {
            if (nums[j] < nums[median]) {
                swap(nums, j, left);
                j++;
                left++;
            } else if (nums[j] > nums[median]) {
                swap(nums, j, right);
                right--;
            } else {
                j++;
            }
        }
        
        int[] temp = new int[n];
        System.arraycopy(nums, 0, temp, 0, n);
        
        // Step 3: wiggle sort
        left = (n - 1) / 2;
        right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                nums[i] = temp[left];
                left--;
            } else {
                nums[i] = temp[right];
                right--;
            }
        }
    }
    
    private int findMedian(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return lo;
        }
        
        int pivot = partition(nums, lo, hi);
        if (pivot == k) {
            return pivot;
        }
        
        if (pivot > k) {
            return findMedian(nums, lo, pivot - 1, k);
        } else {
            return findMedian(nums, pivot + 1, hi, k);
        }
    }
    
    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int i = lo + 1;
        int j = hi;
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] >= pivot) {
                j--;
            }
            
            if (i <= j) {
                swap(nums, i, j);
            }
        }
        
        swap(nums, lo, j);
        
        return j;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Update on 5/20/19:

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: nothing
     */
    public void wiggleSort(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return;
        }
        
        // step 1: find meadian of the array
        int median = findMedian(nums);
        
        // step 2: 3-way partition
        threeWayPartition(nums, median);
        
        // step 3: inter-leave the array
        int[] temp = new int[nums.length];
        int left = (nums.length - 1) / 2;
        int right = nums.length - 1;
        
        for (int i = 0; i < nums.length; i += 2) {
            temp[i] = nums[left];
            left--;
            
            if (right > (nums.length - 1) / 2) {
                temp[i + 1] = nums[right];
                right--;
            }
        }
        
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
    }
    
    private int findMedian(int[] nums) {
        return findMedianHelper(nums, 0, nums.length - 1, (nums.length - 1) / 2);
    }
    
    private int findMedianHelper(int[] nums, int start, int end, int k) {
        if (start == end) {
            return nums[start];
        }
         
        int i = start;
        int j = end;
        int pivot = nums[(i + j) / 2];
         
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
             
            while (i <= j && nums[j] > pivot) {
                j--;
            }
             
            if (i <= j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
         
        if (k <= j) {
            return findMedianHelper(nums, start, j, k);
        } else if (k >= i) {
            return findMedianHelper(nums, i, end, k);
        } else {
            return nums[k];
        }
    }
    
    private void threeWayPartition(int[] nums, int median) {
        int start = 0;
        int end = nums.length - 1;
        int j = 0;
        
        while (j <= end) {
            if (nums[j] < median) {
                swap(nums, start, j);
                start++;
                j++;
            } else if (nums[j] > median) {
                swap(nums, end, j);
                end--;
            } else {
                j++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}