Introduction
LeetCode 324: Wiggle Sort II asks us to reorder an array into a "wiggle" pattern:
css
nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ...
This is different from Wiggle Sort I, as it demands strict alternation of lesser and greater elements. The problem becomes trickier when duplicate elements are present. We aim for an O(n) time and O(1) space solution.
Problem Statement
Given an unsorted array nums, reorder it such that:
nums[0] < nums[1] > nums[2] < nums[3]...
You may assume it is always possible to reorder the array.
Example
python
Input: nums = [1, 5, 1, 1, 6, 4]
Output: [1, 6, 1, 5, 1, 4] # One possible answer
Input: nums = [1, 3, 2, 2, 3, 1]
Output: [2, 3, 1, 3, 1, 2] # One possible answer
🧠 Key Insight
To achieve the wiggle pattern:
- Place larger elements at odd indices (peaks)
- Place smaller elements at even indices (valleys)
If we sort the array and rearrange elements from the ends of the sorted list, we can fill it in a way that maintains the wiggle pattern.
To optimize, we:
- Find the median
- Use a virtual index mapping trick to rearrange the numbers while partitioning around the median (3-way partition like Dutch National Flag problem)
✅ Approach: O(n) Time using Quickselect + Virtual Indexing
Step-by-Step Solution
Step 1: Find the Median (Using Quickselect)
We use nth_element logic (similar to Quickselect) to find the median.
Step 2: Define Virtual Index
python
# Mapping from index to "virtual index" space
def virtual_index(i, n):
return (1 + 2*i) % (n | 1)
This mapping helps us fill odd indices first, which is necessary to avoid adjacent duplicates.
Step 3: 3-Way Partitioning
Like Dutch National Flag, we partition:
- Elements > median to left
- Elements < median to right
- Elements == median stay in center
✅ Python Code
python
class Solution:
def wiggleSort(self, nums: list[int]) -> None:
import random
def find_kth_smallest(k):
def quickselect(left, right):
pivot = nums[random.randint(left, right)]
l, r = left, right
i = left
while i <= r:
if nums[i] < pivot:
nums[i], nums[l] = nums[l], nums[i]
i += 1
l += 1
elif nums[i] > pivot:
nums[i], nums[r] = nums[r], nums[i]
r -= 1
else:
i += 1
if k < l:
return quickselect(left, l - 1)
elif k > r:
return quickselect(r + 1, right)
else:
return nums[k]
return quickselect(0, len(nums) - 1)
n = len(nums)
median = find_kth_smallest(n // 2)
def virtual_index(i):
return (1 + 2 * i) % (n | 1)
left, i, right = 0, 0, n - 1
while i <= right:
vi = virtual_index(i)
if nums[vi] > median:
vleft = virtual_index(left)
nums[vi], nums[vleft] = nums[vleft], nums[vi]
i += 1
left += 1
elif nums[vi] < median:
vright = virtual_index(right)
nums[vi], nums[vright] = nums[vright], nums[vi]
right -= 1
else:
i += 1
💡 Explanation of Virtual Index
The virtual index allows us to fill odd indices first:
- For
n = 6: 1, 3, 5, 0, 2, 4
- Ensures that larger numbers go to odd indices → local peaks
⏱️ Time & Space Complexity
MetricValueTime ComplexityO(n) averageSpace ComplexityO(1) (in-place)
🧪 Dry Run Example
Input: [1, 5, 1, 1, 6, 4]
- Median: 3
- Partition:
- Greater than median → odd indices: [5, 6]
- Less than median → even indices: [1, 1, 1]
- Final:
[1, 6, 1, 5, 1, 4] (valid)
🧠 Key Takeaways
- Use virtual indexing to fill wiggle pattern without conflict
- Think in terms of peaks and valleys
- Combine quickselect and Dutch partitioning for efficient solution
✅ Conclusion
LeetCode 324: Wiggle Sort II is a tricky array manipulation problem that requires smart indexing and partitioning. Understanding virtual indexing and how to map values based on median position is key to solving it efficiently.