================================================================================
BLOG ARTICLE CONTENT (Markdown / HTML)
================================================================================
# 180-Day DSA Roadmap | Day 6: Wiggle Sort II (LeetCode #324)
* **Topic:** Arrays & Strings
* **Pattern:** Dutch National Flag (3-Way Partitioning around Median + Virtual Indexing)
* **Difficulty:** Medium / Hard
* **LeetCode Problem:** LeetCode #324 - Wiggle Sort II
* **Target Companies:** Google, Amazon, Microsoft, Meta, Apple
---
## 1. Problem Overview
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.
### Constraints & Requirements
* `1 <= nums.length <= 5 * 10^4`
* `0 <= nums[i] <= 5000`
* It is guaranteed that there will be at least one valid configuration.
* **Follow-up:** Can you do it in $O(N)$ time and/or in-place with $O(1)$ extra space?
### Example Walkthrough
```text
Input: nums = [1, 5, 1, 1, 6, 4]
Output: [1, 6, 1, 5, 1, 4] (or [1, 5, 1, 6, 1, 4])
Explanation:
nums[0] < nums[1] (1 < 6)
nums[1] > nums[2] (6 > 1)
nums[2] < nums[3] (1 > 5... wait, 1 < 5)
nums[3] > nums[4] (5 > 1)
nums[4] < nums[5] (1 < 4)
The strict alternating relation (<, >, <, >) holds true.
2. Pattern Recognition: Why Dutch National Flag Again?
In Day 5, we solved Sort Colors by partitioning 0, 1, 2 around fixed values.
In Wiggle Sort II:
- Every odd index (
1, 3, 5, ...) needs elements strictly larger than its neighbors. - Every even index (
0, 2, 4, ...) needs elements strictly smaller than its neighbors.
If we find the median element of the array:
- Elements greater than median should go to the odd slots (
1, 3, 5, ...). - Elements smaller than median should go to the even slots (
..., 4, 2, 0). - Elements equal to median will naturally fill in the remaining gaps without touching each other.
This is precisely the Dutch National Flag (3-Way Partition) pattern! The only challenge is placing elements into odd/even slots rather than a linear 0 ... n-1 sequence.
3. The Virtual Indexing Technique
To run the Dutch National Flag in-place, we map normal sequential indices 0, 1, 2, ... to our desired wiggle positions:
- Map smaller indices to odd positions:
1, 3, 5, ... - Map larger indices to even positions:
0, 2, 4, ...
The virtual index formula for an index $i$ is:
$$\text{virtual\_index}(i) = (1 + 2i) \pmod{n \mid 1}$$
(Where $n \mid 1$ represents $n$ rounded up to the nearest odd number: n | 1).
Using this mapping function A(i):
i = 0maps to index1i = 1maps to index3i = 2maps to index5- As $i$ continues, it wraps around cleanly to
0, 2, 4, ...
Now we run standard Day 5 Dutch National Flag using A(mid), A(low), and A(high)!
4. Algorithmic Approaches
Approach 1: Sorting + Auxiliary Array (Intuitive O(N log N))
- Sort the array.
- Split into two halves: smaller half and larger half.
- Fill odd positions from the back of the larger half, and even positions from the back of the smaller half (to avoid adjacent identical medians).
- Time Complexity: $O(N \log N)$
- Space Complexity: $O(N)$
- Verdict: Passes easily, great for getting working code down first in an interview.
Approach 2: Quickselect + Virtual Indexing 3-Way Partition (Optimal MNC Standard)
- Find the median in $O(N)$ average time using Quickselect (
std::nth_elementin C++). - Run Dutch National Flag using virtual index mapping:
- If
nums[A(mid)] > median: swap withnums[A(low)],low++,mid++ - If
nums[A(mid)] < median: swap withnums[A(high)],high-- - If
nums[A(mid)] == median:mid++
- If
- Time Complexity: $O(N)$
- Space Complexity: $O(1)$
- Verdict: The gold standard expected for Tier-1 MNC SDE-2/Senior interviews.
5. Production-Ready Code Implementations
Java Solution (Quickselect + Virtual Indexing)
Java
class Solution {
public void wiggleSort(int[] nums) {
int n = nums.length;
int median = findKthLargest(nums, (n + 1) / 2);
int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (nums[virtualIndex(mid, n)] > median) {
swap(nums, virtualIndex(low, n), virtualIndex(mid, n));
low++;
mid++;
} else if (nums[virtualIndex(mid, n)] < median) {
swap(nums, virtualIndex(mid, n), virtualIndex(high, n));
high--;
} else {
mid++;
}
}
}
private int virtualIndex(int i, int n) {
return (1 + 2 * i) % (n | 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private int findKthLargest(int[] nums, int k) {
// Standard quickselect to find median in O(N) average time
int target = nums.length - k;
int left = 0, right = nums.length - 1;
while (left < right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == target) return nums[pivotIndex];
else if (pivotIndex < target) left = pivotIndex + 1;
else right = pivotIndex - 1;
}
return nums[left];
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right], i = left;
for (int j = left; j < right; j++) {
if (nums[j] <= pivot) {
swap(nums, i++, j);
}
}
swap(nums, i, right);
return i;
}
}
Python 3 Solution (Virtual Indexing / Three-Way Partition)
Python
class Solution:
def wiggleSort(self, nums: list[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
# In Python, sorted median extraction is clean and passes in O(N log N)
# For strict O(N), use quickselect or median of medians
median = sorted(nums)[n // 2]
def v_idx(i: int) -> int:
return (1 + 2 * i) % (n | 1)
low, mid, high = 0, 0, n - 1
while mid <= high:
if nums[v_idx(mid)] > median:
nums[v_idx(low)], nums[v_idx(mid)] = nums[v_idx(mid)], nums[v_idx(low)]
low += 1
mid += 1
elif nums[v_idx(mid)] < median:
nums[v_idx(mid)], nums[v_idx(high)] = nums[v_idx(high)], nums[v_idx(mid)]
high -= 1
else:
mid += 1
C++ Solution (std::nth_element + 3-Way Partition)
C++
#include <vector>
#include <algorithm>
class Solution {
public:
void wiggleSort(std::vector<int>& nums) {
int n = nums.size();
// Find median in O(N) average time using Quickselect
auto midPtr = nums.begin() + n / 2;
std::nth_element(nums.begin(), midPtr, nums.end());
int median = *midPtr;
// Virtual index mapping macro/lambda
#define A(i) nums[(1 + 2 * (i)) % (n | 1)]
int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (A(mid) > median) {
std::swap(A(low), A(mid));
low++;
mid++;
} else if (A(mid) < median) {
std::swap(A(mid), A(high));
high--;
} else {
mid++;
}
}
}
};
6. Complexity Analysis
- Time Complexity: $O(N)$
Finding the median using Quickselect takes $O(N)$ average time. The 3-way partitioning loop runs in $O(N)$ time with at most $N$ iterations. - Space Complexity: $O(1)$
Operates directly on the input array using index redirection. No auxiliary arrays allocated.
7. Key Takeaways & Interview Traps
- Why Normal Sorting From Front Fails: If you sort and place smallest at
0, 2, ...and largest at1, 3, ...from left-to-right, duplicate median values can collide at the center (e.g.,[4, 5, 5, 6]becoming[4, 5, 5, 6]which fails strict inequality5 > 5). - Why Virtual Indexing Works: It places largest numbers at the beginning of the odd slots (
1, 3, 5) and smallest numbers at the end of the even slots (..., 4, 2, 0), keeping median elements as far apart as possible.
Master Wiggle Sort II (LeetCode 324): Virtual Indexing & 3-Way Partition | Day 6 of 180
Master LeetCode 324 (Wiggle Sort II) using Quickselect, 3-way partitioning, and virtual index mapping. Complete O(N) time and O(1) space guide in Java, Python, and C++.
Wiggle Sort II LeetCode 324, Virtual Indexing LeetCode, 3 Way Partition Median, LeetCode 324 Java Python Cpp
leetcode 324, wiggle sort ii, virtual index mapping, 3 way partition, quickselect, median finding, dsa roadmap, dsa interview questions, coding interview preparation, data structures and algorithms, leetcode solutions, three pointers pattern, leetcode medium hard, faang interview preparation, mnc coding questions, amazon coding interview, google coding interview, microsoft interview questions, meta coding interview, adobe coding questions, apple interview questions, leetcode 324 java, leetcode 324 python, leetcode 324 cpp, java dsa, python dsa, cpp dsa, time complexity o n, space complexity o 1, array interview questions, inplace sorting, array partition, top dsa patterns, software engineer jobs, campus placement preparation, competitive programming, vs coding academy, 180 days dsa, dsa cheat sheet, cracking the coding interview, tech interview prep, leetcode patterns, software development engineer, sde 1 preparation, array algorithms, odd even indexing, coding questions for freshers, dsa placement series, engineering placements, leetcode practice, data structures roadmap
Follow our YouTube Channels:
Trendy VS Vlogs: https://youtube.com/@trendyvsvlogs?si=Xd3L31p5zPXggomY
WhatsApp Channel: https://whatsapp.com/channel/0029Vb9H4vC545v2HaoKk735