# 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];
}
}
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]