Wiggle Sort II solution and explanation
Google
9 more videos on this problem
Wiggle Sort 2 | LeetCode 324 Solution ExplainedPepcoding · 14:18 · 18K views
LeetCode 324: Wiggle sort II(Solution)Atriwal Creature · 6:22 · 6K views
Leetcode 324 - Wiggle Sort IIArinc Coding · 13:17 · 3K views
L-48 | Wiggle Sort - II | LeetCode - 324 | Medium | Aditya GoyalAditya Goyal · 5:41 · 1K views
Leetcode Question 324 "Wiggle Sort II" in JavaGhumman Tech · 24:07 · 1K views
Wiggle Sort II | LeetCode 324 | Best Intuition + Optimal Solution (O(n) Approach Explained)Codehurdle · 17:28 · 989 views
Day 325: LeetCode Problem 324. Wiggle Sort II - SwiftiOSxBank · 9:27 · 224 views
LeetCode 324: Wiggle Sort IIAlitaCode · 26:16 · 94 views
No Sound Leetcode 324: Wiggle Sort IIExtremeProgrammer · 1:30 · 64 views
324. Wiggle Sort II | Leetcode Unlocked - PythonLeetcode Unlocked · 4:40 · 30 views
The 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 * 1040 <= nums[i] <= 5000- It is guaranteed that there will be an answer for the given input
nums.
O(n) time and/or in-place with O(1) extra space?Approach overview
Problem Overview: Wiggle Sort II asks you to reorder an array so that nums[0] < nums[1] > nums[2] < nums[3].... The tricky part is handling duplicates while keeping the strict wiggle pattern. A naive rearrangement often breaks when many values are equal, so the solution needs careful placement of small and large elements.
Approach 1: Sort and Merge (O(n log n) time, O(n) space)
The simplest strategy is to sort the array and then interleave the two halves. After sorting, split the array around the median. Place the smaller half in reverse order at even indices and the larger half in reverse order at odd indices. Reversing both halves ensures duplicates don't sit next to each other and break the wiggle condition. This approach relies on sorting and simple array iteration, making it easy to implement in interviews when optimal performance is not required.
Steps: sort the array, compute the midpoint, then iterate through the result array filling even indices from the end of the first half and odd indices from the end of the second half. Time complexity is O(n log n) due to sorting, and extra space O(n) if using a temporary array.
Approach 2: Tri-Partition with Virtual Indexing (O(n) time, O(1) space)
The optimal solution uses a combination of Quickselect and a three-way partition similar to the Dutch National Flag algorithm. First, find the median of the array in O(n) average time using Quickselect. The median becomes the pivot that separates smaller and larger values.
Instead of rearranging elements directly, apply virtual indexing. Map each logical position i to (1 + 2*i) % (n | 1). This mapping places larger elements in odd indices and smaller elements in even indices automatically. Then perform a three-way partition: elements greater than the median move to the front of the virtual order, elements smaller move to the back, and median values stay in the middle.
This technique ensures the final arrangement satisfies nums[0] < nums[1] > nums[2] < nums[3] even when many elements equal the median. The algorithm runs in O(n) time with O(1) extra space and heavily uses concepts from array manipulation and partition-based algorithms.
Recommended for interviews: Start with the sorting-based solution because it demonstrates clear reasoning and is easy to verify. Interviewers usually push for the optimal solution afterward. The Quickselect + virtual indexing method shows deeper understanding of partitioning, index mapping, and in-place algorithms, which is the solution expected at top companies.
Approach 1: Approach 1: Sort and Merge
This approach involves sorting the array and then dividing it into two halves. Afterward, wiggle sort by interleaving elements from each half.
- Sort the entire array.
- Divide the sorted array into two halves.
- Interleave the elements from back to front to meet the wiggle property, ensuring that duplicates are handled correctly.
Time Complexity: O(n log n)
Space Complexity: O(n)
def wiggleSort(nums):
nums.sort()
half = len(nums[::2])
nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]import java.util.*;
public class WiggleSort {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] copy = Arrays.copyOf(nums, n);
int mid = (n - 1) / 2, end = n - 1;
for (int i = 0; i < nums.length; i++) {
nums[i] = (i % 2 == 0) ? copy[mid--] : copy[end--];
}
}
}function wiggleSort(nums) {
nums.sort((a, b) => a - b);
let half = Math.ceil(nums.length / 2);
let firstHalf = nums.slice(0, half).reverse();
let secondHalf = nums.slice(half).reverse();
for (let i = 0, j = 0; i < nums.length; i += 2, j++) {
nums[i] = firstHalf[j];
}
for (let i = 1, j = 0; i < nums.length; i += 2, j++) {
nums[i] = secondHalf[j];
}
}The wiggleSort function sorts the array and splits it evenly into two parts. The first half fills the odd positions in reverse order, and the second half fills the even positions also in reverse.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n) for splitting and temporary arrays.
Approach 2: Approach 2: Tri-Partition with Virtual Indexing
This approach involves using the three-way partitioning technique around the median and arranges elements in a specific virtual order to ensure the wiggle property. This can be done in linear time and in place.
- Find the median of the array using a selection algorithm.
- Reorder the array into three parts: less than, equal to, and greater than the median.
- Use a virtual index mapping to rearrange elements, guaranteeing the wiggle property.
Time Complexity: O(n)
Space Complexity: O(1)
def wiggleSort(nums):
def findKthLargest(k):
import random
def partition(left, right):
pivotIdx = random.randint(left, right)
pivot = nums[pivotIdx]
nums[right], nums[pivotIdx] = nums[pivotIdx], nums[right]
index = left
for i in range(left, right):
if nums[i] > pivot:
nums[i], nums[index] = nums[index], nums[i]
index += 1
nums[index], nums[right] = nums[right], nums[index]
return index
left, right = 0, len(nums) - 1
while left <= right:
pivotIndex = partition(left, right)
if pivotIndex == len(nums) - k:
return nums[pivotIndex]
elif pivotIndex < len(nums) - k:
left = pivotIndex + 1
else:
right = pivotIndex - 1
n = len(nums)
mid = (n + 1) // 2
median = findKthLargest(mid)
left, i, right = 0, 0, n - 1
def virtualIndex(idx):
return (1 + 2 * idx) % (n | 1)
while i <= right:
if nums[virtualIndex(i)] > median:
nums[virtualIndex(left)], nums[virtualIndex(i)] = nums[virtualIndex(i)], nums[virtualIndex(left)]
left += 1
i += 1
elif nums[virtualIndex(i)] < median:
nums[virtualIndex(right)], nums[virtualIndex(i)] = nums[virtualIndex(i)], nums[virtualIndex(right)]
right -= 1
else:
i += 1#include <vector>
#include <algorithm>
#include <cstdlib>
class Solution {
public:
void wiggleSort(std::vector<int>& nums) {
int n = nums.size();
auto midPtr = nums.begin() + n / 2;
std::nth_element(nums.begin(), midPtr, nums.end());
int median = *midPtr;
auto mapping = [&](int i) { return (2 * i + 1) % (n | 1); };
int left = 0, i = 0, right = n - 1;
while(i <= right) {
if(nums[mapping(i)] > median) {
std::swap(nums[mapping(left)], nums[mapping(i)]);
left++; i++;
} else if(nums[mapping(i)] < median) {
std::swap(nums[mapping(right)], nums[mapping(i)]);
right--;
} else {
i++;
}
}
}
};The solution defines functions to utilize quickselect to determine the median. It then rearranges the array using a virtual index mapped with a custom modulo logic to ensure in-place rearrangement with constant space.
Time Complexity: O(n) due to median finding and linear partitioning.
Space Complexity: O(1), as the solution rearranges in place.
Approach 3: Default Approach
func wiggleSort(nums []int) {
n := len(nums)
arr := make([]int, n)
copy(arr, nums)
sort.Ints(arr)
i, j := (n-1)>>1, n-1
for k := 0; k < n; k++ {
if k%2 == 0 {
nums[k] = arr[i]
i--
} else {
nums[k] = arr[j]
j--
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Merge | Time Complexity: O(n log n), due to sorting. |
| Approach 2: Tri-Partition with Virtual Indexing | Time Complexity: O(n) due to median finding and linear partitioning. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Merge | O(n log n) | O(n) | Best for clarity and quick implementation during interviews |
| Tri-Partition with Virtual Indexing (Quickselect) | O(n) | O(1) | Optimal solution when strict wiggle ordering and in-place rearrangement are required |
Frequently asked questions
Is Wiggle Sort II easy or hard?
Wiggle Sort II is generally considered a medium-to-hard array problem. The basic sorted approach is straightforward, but the optimal O(n) in-place solution requires understanding Quickselect, three-way partitioning, and virtual index mapping.
How to solve Wiggle Sort II in O(n)?
First find the median using Quickselect in O(n) average time. Then apply a three-way partition around the median while accessing elements through a virtual index mapping (1 + 2*i) % (n | 1). This mapping places larger numbers at odd indices and smaller numbers at even indices, producing the required wiggle order.
Wiggle Sort II Python or Java solution
Both Python and Java implementations usually follow either the sort-and-interleave approach or the Quickselect partition approach. Python versions often rely on built-in sorting for the simple solution, while optimized implementations replicate the virtual indexing and three-way partition logic used in C++ or Java.
What is the best approach for Wiggle Sort II?
The most efficient approach uses Quickselect to find the median and then performs a three-way partition with virtual indexing. This guarantees the wiggle pattern while handling duplicates correctly. The algorithm runs in O(n) time with O(1) extra space, making it the optimal solution expected in advanced interviews.
What data structure is used in Wiggle Sort II?
The problem mainly uses arrays with advanced manipulation techniques. The optimal solution combines Quickselect for median selection and a three-way partition similar to the Dutch National Flag algorithm while applying a virtual index mapping.
What is the time complexity of Wiggle Sort II?
Two common solutions exist. The sorting-based method runs in O(n log n) time because it sorts the array before rearranging elements. The optimal approach uses Quickselect and a Dutch National Flag style partition to achieve O(n) average time with constant extra space.
Is Wiggle Sort II asked at Google, Amazon, or Meta?
Wiggle Sort II is a well-known interview problem at large tech companies including Google, Meta, and Amazon. It tests understanding of array partitioning, Quickselect, and in-place rearrangement techniques beyond basic sorting.