Skip to main content
Talentd

Wiggle Sort II - Solution & Explanation

MediumArrayDivide and ConquerGreedySorting8 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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?

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.

  1. Sort the entire array.
  2. Divide the sorted array into two halves.
  3. 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)

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.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n) for splitting and temporary arrays.

Try this approach in the editor →

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.

  1. Find the median of the array using a selection algorithm.
  2. Reorder the array into three parts: less than, equal to, and greater than the median.
  3. Use a virtual index mapping to rearrange elements, guaranteeing the wiggle property.

Time Complexity: O(n)
Space Complexity: O(1)

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n) due to median finding and linear partitioning.
Space Complexity: O(1), as the solution rearranges in place.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sort and Merge

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n) for splitting and temporary arrays.

Approach 2: Tri-Partition with Virtual Indexing

Time Complexity: O(n) due to median finding and linear partitioning.
Space Complexity: O(1), as the solution rearranges in place.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and MergeO(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

Video Solution

Wiggle Sort 2 | LeetCode 324 Solution Explained • Pepcoding • 18,953 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Wiggle Sort II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Array With Elements Not Equal to Average of Neighbors

Next

Kth Largest Element in an Array