Solution For Wiggle Sort Ii

Problem statement:
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: [1,6,1,5,1,4] Explanation: This is a zigzag like pattern.

Approach:
To solve this problem, we have to first sort the array using two pointers method (quick sort) then change the sequences to satisfy the required condition. In the required condition, if we look at the sequence, the even index should have the value greater or equal than the previous odd index value and less or equal to the next odd index value. The same applies to the odd index values.

Algorithm:
1. Sort the array.
2. Set two pointers p1 and p2 at index (n-1)/2 and n-1, respectively.
3. Create a new array result.
4. For each element in the result array, if the index is even, assign nums[p1] to it and decrement p1. If the index is odd, assign nums[p2] to it and decrement p2.
5. Return the result.

Pseudo code:
def wiggleSort(nums):
nums.sort()
p1 = (len(nums)-1)//2
p2 = len(nums)-1
result = [0] * len(nums)
for i in range(len(nums)):
if i % 2 == 0:
result[i] = nums[p1] p1 -= 1
else:
result[i] = nums[p2] p2 -= 1
return result

Time complexity: O(nlogn) due to sorting the array.
Space complexity: O(n) for creating a new array for the result.

Code in Python:

class Solution:
def wiggleSort(self, nums: List[int]) -> None:
“””
Do not return anything, modify nums in-place instead.
“””
nums.sort()
p1 = (len(nums)-1)//2
p2 = len(nums)-1

    result = [0] * len(nums)
    for i in range(len(nums)):
        if i % 2 == 0:
            result[i] = nums[p1]
            p1 -= 1
        else:
            result[i] = nums[p2]
            p2 -= 1

    nums[:] = result[:] # Update nums with the result

Step by Step Implementation For Wiggle Sort Ii

class Solution {
    public void wiggleSort(int[] nums) {
        //find median
        int median = findKthLargest(nums, (nums.length + 1) / 2);
        //index-based mapping to rearrange elements to three groups
        int n = nums.length;
        int left = 0, i = 0, right = n - 1;
        while (i <= right) {
            if (nums[newIndex(i,n)] > median) {
                swap(nums, newIndex(left++,n), newIndex(i++,n));
            }
            else if (nums[newIndex(i,n)] < median) {
                swap(nums, newIndex(right--,n), newIndex(i,n));
            }
            else {
                i++;
            }
        }
    }
    
    //3-way partitioning
    private int findKthLargest(int[] nums, int k) {
        shuffle(nums);
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }
    
    //Fisher-Yates shuffle
    private void shuffle(int a[]) {
        final Random random = new Random();
        for(int ind = 1; ind < a.length; ind++) {
            final int r = random.nextInt(ind + 1);
            swap(a, ind, r);
        }
    }
    
    //3-way partitioning helper
    private int partition(int[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        while(true) {
            while(i < hi && less(a[++i], a[lo]));
            while(j > lo && less(a[lo], a[--j]));
            if(i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }
    
    //helper function for comparing two values
    private boolean less(int v, int w) {
        return v < w;
    }
    
    //helper function for swapping two values
    private void swap(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    
    //helper function that generates new index
    private int newIndex(int index, int n) {
        return (1 + 2*index) % (n | 1);
    }
}

def wiggleSort(nums):
    
    # sort the list in ascending order
    nums.sort()
    
    # take the median as the pivot element
    pivot = nums[len(nums)//2]
    
    # create three empty lists to store the elements less than, equal to, and greater than the pivot
    less, equal, greater = [], [], []
    
    # iterate through the nums list and append the elements to the appropriate list
    for num in nums:
        if num < pivot:
            less.append(num)
        elif num > pivot:
            greater.append(num)
        else:
            equal.append(num)
    
    # combine the three lists back into one and return the result
    return less + equal + greater

var wiggleSort = function(nums) {
    nums.sort(function(a, b){return a-b});
    var i=0, j=Math.floor(nums.length/2), k=nums.length-1;
    while(i <= k){
        if(i === k){
            nums[i] = nums[j];
        }else{
            nums[i] = nums[j];
            nums[i+1] = nums[k];
        }
        i+=2;
        j++;
        k--;
    }
};

class Solution {
public:
    void wiggleSort(vector& nums) {
        // Find a median.
        auto midptr = nums.begin() + nums.size() / 2;
        nth_element(nums.begin(), midptr, nums.end());
        int mid = *midptr;

        // Index-rewiring.
#define A(i) nums[(1+2*(i)) % (nums.size()|1)]

        // 3-way-partition-to-wiggly in O(n) time with O(1) space.
        int i = 0, j = 0, n = nums.size();
        while (j <= n) {
            if (A(j) > mid)
                swap(A(i++), A(j++));
            else if (A(j) < mid)
                swap(A(j), A(n--));
            else
                j++;
        }
    }
};

public class Solution {
    public void WiggleSort(int[] nums) {
        // Sort the array first
        Array.Sort(nums);
        
        // Create a new array to store the wiggle-sorted elements
        int[] wiggle = new int[nums.Length];
        
        // Index to track the current position in the wiggle array
        int index = 0;
        
        // Iterate through the array from both ends
        for(int i = 0, j = nums.Length - 1; i <= j; i++, j--){
            // Store the smaller element at even indices in the wiggle array
            wiggle[index] = nums[i];
            index += 2;
            
            // If we haven't reached the middle of the array yet,
            // store the larger element at odd indices in the wiggle array
            if(i != j){
                wiggle[index] = nums[j];
                index += 2;
            }
        }
        
        // Copy the wiggle-sorted array back into the original array
        for(int i = 0; i < nums.Length; i++){
            nums[i] = wiggle[i];
        }
    }
}