Wiggle Sort - Solution & Explanation

Problem Overview: Given an integer array, rearrange it so the numbers follow a wiggle pattern: nums[0] <= nums[1] >= nums[2] <= nums[3].... The goal is not to fully sort the array but to ensure alternating peaks and valleys between adjacent elements.

Approach 1: Sort and Swap Adjacent Pairs (O(n log n) time, O(1) space)

Sort the array first using a standard algorithm. After sorting, the array is strictly increasing. To create the wiggle pattern, iterate from index 1 and swap every pair (i, i+1). This creates local peaks at odd indices because each swapped element becomes larger than its neighbors. The logic relies on the sorted order guaranteeing that adjacent elements remain valid after the swap. This approach uses sorting and is straightforward to reason about, though it performs extra work compared to the optimal solution.

Approach 2: Single Pass Greedy Swap (O(n) time, O(1) space)

Traverse the array once and enforce the wiggle rule locally. For every index i, check whether the relationship with i-1 matches the required pattern. If i is odd, ensure nums[i] >= nums[i-1]. If i is even, ensure nums[i] <= nums[i-1]. When the condition fails, swap the two elements. This local correction guarantees the global wiggle structure because fixing each pair does not break the previous constraint. The algorithm uses a greedy strategy: enforce the correct relationship at each step without revisiting earlier indices. Since every element is processed once, the time complexity is linear.

Approach 3: Local Peak Enforcement with Neighbor Checks (O(n) time, O(1) space)

Another view of the greedy idea treats odd indices as peaks. Iterate through the array and ensure each odd index is greater than or equal to both neighbors. If the left neighbor is larger, swap with it. If the right neighbor is larger, swap with it. This method explicitly enforces the peak structure instead of alternating comparisons. The logic still operates in a single pass and relies on constant-time swaps within the array. It produces the same wiggle property but with slightly more condition checks.

Recommended for interviews: The single-pass greedy approach is what interviewers typically expect. It demonstrates that you recognize the wiggle property can be enforced locally instead of globally sorting the array. Mentioning the sorting approach first shows baseline problem understanding, but implementing the O(n) greedy swap shows stronger algorithmic insight.