# Wiggle Sort II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/wiggle-sort-ii)
Canonical: https://scaleengineer.com/dsa/problems/wiggle-sort-ii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting), [Quickselect](https://scaleengineer.com/algorithms/quickselect)
**Data structures:** Array
---
## Problem
Given an integer array `nums`, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]...`.

You may assume the input array always has a valid answer.

**Example 1:**

**Input:** nums = [1,5,1,1,6,4]
**Output:** [1,6,1,5,1,4]
**Explanation:** [1,4,1,5,1,6] is also accepted.

**Example 2:**

**Input:** nums = [1,3,2,2,3,1]
**Output:** [2,3,1,3,1,2]

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `0 <= nums[i] <= 5000`
* It is guaranteed that there will be an answer for the given input `nums`.

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

# Approaches
## Brute Force by Generating All Permutations
This approach involves generating every possible arrangement (permutation) of the input array `nums`. For each permutation, we check if it satisfies the wiggle sort condition (`nums[0] < nums[1] > nums[2] < ...`). The first permutation that meets the condition is the answer.
**Time:** O(N! * N). There are N! permutations, and checking each one takes O(N) time. · **Space:** O(N) for the recursion stack and to store the current permutation.
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find a solution if one exists.
**Cons:** Extremely high time complexity, making it infeasible for all but the smallest input sizes (e.g., N > 10).; Generates a massive number of possibilities, most of which are incorrect.
### Explanation
The brute-force method systematically explores all possible orderings of the numbers in the input array. This is typically done using a recursive algorithm that builds permutations. For each complete permutation, a separate check is performed to see if it adheres to the alternating less-than/greater-than pattern. While this approach is guaranteed to find a solution if one exists, its computational cost is prohibitive due to the factorial growth of the number of permutations.

For an array of size `N`, there are `N!` (N factorial) possible permutations. For each one, we must perform `N-1` comparisons to validate the wiggle property. This leads to a total time complexity of `O(N * N!)`, which is not practical for the given constraints.

```java
// This is a conceptual illustration. 
// Running this code would be too slow for the given constraints.
class Solution {
    private int[] result;

    public void wiggleSort(int[] nums) {
        // A helper array to mark used elements for permutation generation
        boolean[] used = new boolean[nums.length];
        // A list to build the current permutation
        java.util.List<Integer> p = new java.util.ArrayList<>();
        // Sort nums to handle duplicates correctly in permutation generation
        java.util.Arrays.sort(nums);
        generatePermutations(nums, used, p);
        // Copy the found result back to nums
        for (int i = 0; i < nums.length; i++) {
            nums[i] = result[i];
        }
    }

    private void generatePermutations(int[] nums, boolean[] used, java.util.List<Integer> p) {
        if (result != null) return; // Stop if a solution is already found

        if (p.size() == nums.length) {
            if (isWiggle(p)) {
                result = p.stream().mapToInt(i -> i).toArray();
            }
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // Standard permutation logic to handle duplicates
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            p.add(nums[i]);
            generatePermutations(nums, used, p);
            p.remove(p.size() - 1);
            used[i] = false;
        }
    }

    private boolean isWiggle(java.util.List<Integer> p) {
        for (int i = 0; i < p.size() - 1; i++) {
            if (i % 2 == 0) {
                if (p.get(i) >= p.get(i + 1)) return false;
            } else {
                if (p.get(i) <= p.get(i + 1)) return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Generate all distinct permutations of the input array `nums`.
- For each permutation, create a helper function `isWiggle(arr)` that iterates from the beginning of the array to the second-to-last element.
- Inside `isWiggle`, check if the wiggle condition `(i % 2 == 0 && arr[i] < arr[i+1]) || (i % 2 != 0 && arr[i] > arr[i+1])` holds for all `i`.
- If the condition is ever violated, the permutation is not a wiggle sort, so return `false`.
- If the loop completes, it's a valid wiggle sort, return `true`.
- The first permutation for which `isWiggle` returns `true` is the answer. Since the problem guarantees an answer exists, one will be found.

## Sort and Interleave
A much more efficient approach is to first sort the array. A sorted array gives us a clear separation of small and large numbers. The smaller half of the numbers should occupy the even indices (which are "small" positions in the wiggle pattern), and the larger half should occupy the odd indices ("large" positions). To prevent adjacent elements from being equal (e.g., if the median value is repeated), we fill the elements in a specific order from a sorted copy.
**Time:** O(N log N) dominated by the sorting step. The filling process takes O(N) time. · **Space:** O(N) to store the copy of the array.
**Pros:** Significantly more efficient than the brute-force approach.; Relatively straightforward to implement once the sorting idea is established.; Correctly handles cases with duplicate numbers, including the median.
**Cons:** Requires extra space proportional to the input size, which might be a concern for very large inputs.; The time complexity is dominated by sorting, so it's not a linear-time solution.
### Explanation
This method leverages sorting to simplify the problem. Once the array is sorted, we know which numbers are small and which are large. The core idea is to interleave the smaller half of the numbers with the larger half.

Let the sorted array be `s`. The first `(n+1)/2` elements are the 'small group' and the remaining `n/2` elements are the 'large group'. We want to place the large group at odd indices (`nums[1], nums[3], ...`) and the small group at even indices (`nums[0], nums[2], ...`).

A naive interleaving might fail if the median value is repeated. For example, with sorted `[4, 5, 5, 6]`, putting `[4, 5]` at even indices and `[5, 6]` at odd indices could result in `[4, 5, 5, 6]`, which fails because `5` is not greater than `5`. 

The key is the filling order. By filling the odd-indexed 'large' slots from the end of the sorted array and then filling the even-indexed 'small' slots with the rest, we ensure that the median values are separated, thus satisfying the strict inequality.

```java
import java.util.Arrays;

class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        // Create a copy and sort it
        int[] temp = Arrays.copyOf(nums, n);
        Arrays.sort(temp);
        
        // Pointer to the end of the sorted array
        int j = n - 1;
        
        // Fill odd indices from the end of the sorted array (largest elements)
        for (int i = 1; i < n; i += 2) {
            nums[i] = temp[j--];
        }
        
        // Fill even indices with the remaining elements (smallest elements)
        for (int i = 0; i < n; i += 2) {
            nums[i] = temp[j--];
        }
    }
}
```
### Algorithm
- Create a temporary array, `temp`, as a copy of the input array `nums`.
- Sort the `temp` array in ascending order. This takes `O(N log N)` time.
- Let `n` be the length of the array. The smaller half of the numbers are `temp[0...m-1]` and the larger half are `temp[m...n-1]`, where `m = (n+1)/2`.
- To ensure strict inequality, we must place the numbers carefully. We fill the final array by picking from the ends of the sorted `temp` array.
- Initialize a pointer `j` to `n-1` (the largest element in `temp`).
- Fill the odd indices (`1, 3, 5, ...`) of the original `nums` array with elements from the large half of `temp`, starting from the largest (`temp[n-1]`, `temp[n-2]`, ...).
- Then, fill the even indices (`0, 2, 4, ...`) of `nums` with the remaining elements (the small half), also starting from the largest among them.

## Linear Time In-Place Solution with Virtual Indexing
This optimal approach achieves `O(N)` time and `O(1)` space complexity, meeting the follow-up challenge. It avoids a full sort by finding the median element in linear time. Then, it uses a clever "virtual indexing" scheme to place elements correctly in-place. The idea is to partition the array into three groups: elements larger than the median, equal to the median, and smaller than the median. This partitioning is done on a "virtual" array that maps indices `0, 1, 2, ...` to the desired wiggle positions `1, 3, 5, ..., 0, 2, 4, ...`.
**Time:** O(N) on average. Finding the median with Quickselect is O(N) on average. The 3-way partition is a single pass, which is O(N). · **Space:** O(1) extra space. The Quickselect can be performed in-place. The recursive calls for Quickselect would take O(log N) stack space on average.
**Pros:** Optimal time complexity of O(N) on average.; Optimal space complexity of O(1) (if Quickselect is done in-place on the original array, which is valid here).; Satisfies the follow-up constraints of the problem.
**Cons:** The logic, especially the virtual index mapping and in-place partitioning, is complex and non-intuitive.; Implementation is error-prone. A standard Quickselect has an `O(N^2)` worst-case time, though this is rare in practice.
### Explanation
This advanced solution directly constructs the wiggle-sorted array without a full sort or an auxiliary array. 

1.  **Median Finding:** The first step is to find the value that partitions the numbers into two halves. This value is the median. We can find the `k`-th smallest element in an array in `O(N)` average time using the Quickselect algorithm. For this problem, we need the `(n+1)/2`-th smallest element.

2.  **Virtual Indexing and Partitioning:** The core of the solution is to place all numbers larger than the median in the 'large' slots (odd indices) and all numbers smaller than the median in the 'small' slots (even indices). The numbers equal to the median will fill the remaining slots. This is achieved simultaneously using a single pass with the 3-way partition algorithm combined with virtual indexing. The mapping `A(i) = (1 + 2*i) % (n | 1)` ensures that as we iterate through `i` from `0` to `n-1`, we are considering positions in the order of `odd_indices..., even_indices...`. By partitioning based on this virtual layout, we move larger elements to the start of this virtual sequence (odd indices) and smaller elements to the end (even indices), achieving the wiggle sort in-place.

```java
class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return;
        }

        // Step 1: Find the median element. The median is the (n+1)/2-th smallest element.
        int median = findKthSmallest(nums, (n + 1) / 2);

        // Step 2: 3-way partition using virtual indexing.
        int left = 0, i = 0, right = n - 1;

        while (i <= right) {
            int mapped_i = mapIndex(i, n);
            if (nums[mapped_i] > median) {
                int mapped_left = mapIndex(left, n);
                swap(nums, mapped_i, mapped_left);
                left++;
                i++;
            } else if (nums[mapped_i] < median) {
                int mapped_right = mapIndex(right, n);
                swap(nums, mapped_i, mapped_right);
                right--;
            } else {
                i++;
            }
        }
    }

    // Maps an index i to its corresponding position in the wiggle-sorted array.
    private int mapIndex(int i, int n) {
        // n | 1 ensures the modulus is always odd, which is key to the mapping.
        return (1 + 2 * i) % (n | 1);
    }

    // Finds the k-th smallest element using Quickselect (O(N) average time).
    private int findKthSmallest(int[] nums, int k) {
        int[] temp = nums.clone(); // Use a copy to not disrupt the original array before partitioning
        int targetIndex = k - 1; // Convert 1-based k to 0-based index
        int left = 0, right = temp.length - 1;

        while (left <= right) {
            int pivotIndex = partition(temp, left, right);
            if (pivotIndex == targetIndex) {
                return temp[pivotIndex];
            } else if (pivotIndex < targetIndex) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
        return -1; // Should not be reached
    }

    // Lomuto partition scheme for Quickselect.
    private int partition(int[] nums, int left, int right) {
        int pivotValue = nums[right];
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, right, storeIndex);
        return storeIndex;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- **Find Median:** Use an `O(N)` average time selection algorithm (like Quickselect) to find the median element of the array. The median is the `(n+1)/2`-th smallest element, which separates the array into a smaller half and a larger half.
- **Virtual Indexing:** Define a mapping function `map(i) = (1 + 2*i) % (n | 1)` where `n` is the array length. This function maps indices `0, 1, 2, ...` to the desired wiggle positions `1, 3, 5, ..., 0, 2, 4, ...`. This places elements for the 'large' slots first, followed by elements for the 'small' slots.
- **3-Way Partition:** Perform a 3-way partition (Dutch National Flag algorithm) on the array in-place. Instead of accessing elements by their direct index `i`, use the virtual index `map(i)`. This partitions the array into three groups based on the median: elements larger than the median, elements equal to the median, and elements smaller than the median. The virtual indexing ensures they are placed into the correct final wiggle positions.

# Solutions
### Java

```java
class Solution {
public
  void wiggleSort(int[] nums) {
    int[] arr = nums.clone();
    Arrays.sort(arr);
    int n = nums.length;
    int i = (n - 1) >> 1, j = n - 1;
    for (int k = 0; k < n; ++k) {
      if (k % 2 == 0) {
        nums[k] = arr[i--];
      } else {
        nums[k] = arr[j--];
      }
    }
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var wiggleSort =
  function (nums) {
    let bucket = new Array(5001).fill(0);
    for (const v of nums) {
      bucket[v]++;
    }
    const n = nums.length;
    let j = 5000;
    for (let i = 1; i < n; i += 2) {
      while (bucket[j] == 0) {
        --j;
      }
      nums[i] = j;
      --bucket[j];
    }
    for (let i = 0; i < n; i += 2) {
      while (bucket[j] == 0) {
        --j;
      }
      nums[i] = j;
      --bucket[j];
    }
  };

```

### CPP

```cpp
class Solution {
public:
  void wiggleSort(vector<int> &nums) {
    vector<int> arr = nums;
    sort(arr.begin(), arr.end());
    int n = nums.size();
    int i = (n - 1) >> 1, j = n - 1;
    for (int k = 0; k < n; ++k) {
      if (k % 2 == 0)
        nums[k] = arr[i--];
      else
        nums[k] = arr[j--];
    }
  }
};

```

### Python

```python
''' >>> nums = list(range(1,11)) >>> nums [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] >>> nums[::2] [1, 3, 5, 7, 9] >>> nums[1::2] [2, 4, 6, 8, 10] >>> >>> mid = (len(nums) - 1) // 2 >>> mid 4 >>> nums[mid::-1] [5, 4, 3, 2, 1] >>> nums[:mid:-1] [10, 9, 8, 7, 6] >>> >>> nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1] >>> nums [5, 10, 4, 9, 3, 8, 2, 7, 1, 6] >>> ''' class Solution : def wiggleSort ( self , nums : List [ int ]) -> None : """ Do not return anything, modify nums in-place instead. """ n = len ( nums ) nums . sort () mid = ( n - 1 ) // 2 nums [:: 2 ], nums [ 1 :: 2 ] = nums [ mid :: - 1 ], nums [: mid : - 1 ] # better to have descending list, below having error # input: [4,5,5,6], below line output: [4,5,5,6] # nums[::2], nums[1::2] = nums[:mid+1:1], nums[mid+1::1] ''' >>> nums=[4,5,5,6] >>> mid = (len(nums) - 1) // 2 >>> >>> nums[::2] [4, 5] >>> nums[1::2] [5, 6] >>> nums[mid::-1] [5, 4] >>> nums[:mid:-1] [6, 5] >>> nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1] >>> nums [5, 6, 4, 5] ''' class Solution : # extra space def wiggleSort ( self , nums : List [ int ]) -> None : """ Do not return anything, modify nums in-place instead. """ arr = sorted ( nums ) # extra O(N) space n = len ( arr ) i , j = ( n - 1 ) >> 1 , n - 1 for k in range ( n ): if k % 2 == 0 : nums [ k ] = arr [ i ] i -= 1 else : nums [ k ] = arr [ j ] j -= 1 class Solution : # quicksort, without full sort def wiggleSort ( self , nums : List [ int ]) -> None : """ Do not return anything, modify nums in-place instead. """ n = len ( nums ) if n <= 1 : return mid = self . findKthLargest ( nums , ( n + 1 ) // 2 ) def idx ( i ): return ( 2 * i + 1 ) % ( n | 1 ) i , j , k = 0 , 0 , n - 1 while j <= k : if nums [ idx ( j )] > mid : nums [ idx ( i )], nums [ idx ( j )] = nums [ idx ( j )], nums [ idx ( i )] i += 1 j += 1 elif nums [ idx ( j )] < mid : nums [ idx ( j )], nums [ idx ( k )] = nums [ idx ( k )], nums [ idx ( j )] k -= 1 else : j += 1 def findKthLargest ( self , nums : List [ int ], k : int ) -> int : n = len ( nums ) left , right = 0 , n - 1 while True : pivotIdx = self . partition ( nums , left , right ) if pivotIdx == k - 1 : return nums [ pivotIdx ] elif pivotIdx < k - 1 : left = pivotIdx + 1 else : right = pivotIdx - 1 def partition ( self , nums , left , right ): pivot = nums [ left ] l , r = left + 1 , right while l <= r : if nums [ l ] < pivot and nums [ r ] > pivot : nums [ l ], nums [ r ] = nums [ r ], nums [ l ] l += 1 r -= 1 elif nums [ l ] >= pivot : l += 1 else : r -= 1 nums [ left ], nums [ r ] = nums [ r ], nums [ left ] return r
```