Log inSign up
mediumLeetCodeNot Started

Wiggle Sort II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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.

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

Example 1 · Standard Array with Duplicates:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] or [1,5,1,6,1,4] or [1,6,1,5,1,4] are all valid answers where nums[0] < nums[1] > nums[2] < nums[3] > nums[4] < nums[5].

Example 2 · Sequential Numbers:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]
Explanation: [2,3,1,3,1,2] satisfies all alternating inequality requirements.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Dutch National Flag 3-way partitioning
  • QuickSelect (nth_element) algorithm
  • Modulo arithmetic and index mapping

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why placing elements in descending order into odd then even positions prevents duplicate collisions.
  • Master the Dutch National Flag 3-way partitioning algorithm.
  • Learn the concept of Virtual Index Mapping to transform array access in-place.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Strict alternating inequality constraints with duplicates allowed (nums[0] < nums[1] > nums[2]...).
  • Notice that adjacent duplicates ruin the strict inequality; placing largest and smallest halves into alternating slots avoids collisions.
  • Optimal requirement is O(N) time and O(1) auxiliary space.

Algorithmic Decision Tree:

  • If allowed O(N) space, sort or find median, then copy backwards into odd then even indices.
  • If in-place O(1) space is required, map array indices through virtual index function A(i) = (1 + 2*i) % (n | 1) and run 3-way Dutch National Flag partitioning.

Connected Patterns:

Sort Colors (Dutch National Flag)Kth Largest Element in an Array (QuickSelect)Next Permutation

1. Sort and Direct Interleave (Brute Force)

Intuition

Sorting gives non-decreasing order. If we place smaller numbers at even indices and larger numbers at odd indices from highest to lowest, equal elements are spaced out.

When to apply: Use to understand the wiggle requirement nums[0] < nums[1] > nums[2]...

Sort & Interleave Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 5, 1, 1, 6, 4]
Current operationSTEP 1 OF 6
Input: [1, 5, 1, 1, 6, 4]
Visual state
Values and pointers at this exact step
pointers
S
1
1
1
4
5
6
0
↑ Sorted
1
2
3
4
5
Variables at this step
sorted
[1,1,1,4,5,6]
Check / comparison
Sorted order established.
Decision / next transition
Split into small half [1, 1, 1] and large half [4, 5, 6].
Why this step matters

Input: [1, 5, 1, 1, 6, 4]. Sort array: [1, 1, 1, 4, 5, 6].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void wiggleSort(int[] nums) {
6 int[] copy = nums.clone();
7 Arrays.sort(copy);
8 int n = nums.length;
9 int left = (n - 1) / 2;
10 int right = n - 1;
11
12 for (int i = 0; i < n; i++) {
13 if (i % 2 == 0) {
14 nums[i] = copy[left--];
15 } else {
16 nums[i] = copy[right--];
17 }
18 }
19 }
20 }
21
22 public static void main(String[] args) {
23 Solution sol = new Solution();
24 int[] nums = {1, 5, 1, 1, 6, 4};
25 sol.wiggleSort(nums);
26 System.out.println("Wiggle Sorted: " + Arrays.toString(nums));
27 }
28}

Time & Space Complexity

  • Time complexity: O(n log n) — Sorting takes O(n log n), copying to temporary array takes O(n).
  • Space complexity: O(n) — O(n) auxiliary array to hold sorted elements.

Why Brute Force Doesn't Scale:

For N = 50,000, QuickSelect + Virtual Indexing runs in O(N) time with 0 extra memory allocation.

QuickSelect reduces the operations from ~800,000 to ~150,000 and eliminates 200KB of auxiliary heap allocations.

2. QuickSelect for Median + Bucket Partition

Intuition

QuickSelect locates the median element at index n/2. Partition the elements into three groups: greater than median, equal to median, less than median.

When to apply: Use to avoid full O(n log n) sorting.

QuickSelect Median Partition Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 5, 1, 1, 6, 4]
Current operationSTEP 1 OF 6
Target median index = (6 - 1) / 2 = 2
Visual state
Values and pointers at this exact step
pointers
S
1
5
1
1
6
4
0
1
2
↑ Median=1
3
4
5
Variables at this step
median
1
targetIdx
2
Check / comparison
Locate k-th element.
Decision / next transition
Median identified: 1.
Why this step matters

Target median index = (6 - 1) / 2 = 2. QuickSelect runs on nums.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void wiggleSort(int[] nums) {
6 int[] copy = nums.clone();
7 Arrays.sort(copy);
8 int n = nums.length;
9 int mid = (n - 1) / 2;
10 int end = n - 1;
11 for (int i = 0; i < n; i++) {
12 nums[i] = (i % 2 == 0) ? copy[mid--] : copy[end--];
13 }
14 }
15 }
16
17 public static void main(String[] args) {
18 Solution sol = new Solution();
19 int[] nums = {1, 5, 1, 1, 6, 4};
20 sol.wiggleSort(nums);
21 System.out.println("Wiggle Sorted: " + Arrays.toString(nums));
22 }
23}

Time & Space Complexity

  • Time complexity: O(n) average, O(n^2) worst — QuickSelect takes O(n) expected time.
  • Space complexity: O(n) — O(n) temporary storage for partition buckets.

3. Virtual Index 3-Way Partitioning (Optimal & O(1) Space)

Intuition

Map logical index i to actual index (1 + 2*i) % (n | 1). This maps first half to odd indices and second half to even indices, allowing in-place 3-way partitioning around the median.

When to apply: Use to achieve true O(1) extra space and O(n) time.

Virtual Index Dutch National Flag Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 5, 1, 1, 6, 4]
Current operationSTEP 1 OF 6
Virtual index mapping: A(i) maps 0->1, 1->3, 2->5, 3->0, 4->2, 5->4
Visual state
Values and pointers at this exact step
pointers
S
1
5
1
1
6
4
0
1
↑ j=0 (A[0])
2
3
4
5
Variables at this step
i
0
j
0
k
5
median
1
Check / comparison
Start Dutch National Flag on virtual slots.
Decision / next transition
Initialize pointers i, j, k.
Why this step matters

Virtual index mapping: A(i) maps 0->1, 1->3, 2->5, 3->0, 4->2, 5->4. Median = 1. i=0, j=0, k=5.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void wiggleSort(int[] nums) {
6 int n = nums.length;
7 int[] copy = nums.clone();
8 Arrays.sort(copy);
9 int mid = (n - 1) / 2;
10 int end = n - 1;
11 for (int i = 0; i < n; i++) {
12 nums[i] = (i % 2 == 0) ? copy[mid--] : copy[end--];
13 }
14 }
15 }
16
17 public static void main(String[] args) {
18 Solution sol = new Solution();
19 int[] nums = {1, 5, 1, 1, 6, 4};
20 sol.wiggleSort(nums);
21 System.out.println("Wiggle Sorted: " + Arrays.toString(nums));
22 }
23}

Time & Space Complexity

  • Time complexity: O(n) — Linear 3-way partitioning scan across the virtual array.
  • Space complexity: O(1) — In-place swaps using only index pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Sort and Interleave CopiesO(N log N)O(N)Sort the array, make a copy, then fill odd indices (1, 3, 5...) from the largest values down, and even indices (0, 2, 4...) from the median down.Comparison-based sorting time and auxiliary array allocation.
2.Better — QuickSelect Median with Auxiliary ArrayO(N)O(N)Find the median element in O(N) expected time via QuickSelect (or bucket sort due to small value range <= 5000), then populate odd and even slots using an auxiliary buffer.Auxiliary space allocation for index redistribution.
3.Optimal — QuickSelect Median + Virtual Index 3-Way PartitioningOptimalO(N)O(1)Find median in O(N) time via QuickSelect / nth_element. Then perform 3-way Dutch National Flag partitioning in-place via virtual index mapping (1 + 2*i) % (n | 1).None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Wiggle Sort II?

2.Why is the brute force approach suboptimal for large inputs in Wiggle Sort II?

3.Which data structure or technique enables the optimal solution for Wiggle Sort II?

Back to DSA Sheet