Wiggle Sort - Solution & Explanation

Problem Overview: You are given an integer array and must reorder it in-place so that it follows a wiggle pattern: nums[0] <= nums[1] >= nums[2] <= nums[3] .... Any valid arrangement that satisfies the alternating relationship is acceptable.

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

The most direct solution starts by sorting the array. After sorting, iterate through the array starting from index 1 and swap every pair (i, i+1). Because the array is sorted, swapping adjacent elements creates the alternating high-low pattern required for wiggle order. This approach relies on sorting to guarantee that each local pair satisfies the condition after swapping. It’s easy to implement and works reliably, though the O(n log n) sorting step makes it slower than necessary.

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

A more efficient method scans the array once and fixes violations locally. For each index i, check whether the wiggle condition is satisfied. 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 works because fixing the local pair does not break the previously established pattern. The technique is a classic greedy strategy: enforce the constraint immediately while iterating through the array. Since each element is visited once and swaps are constant-time, the total complexity is O(n) with O(1) extra space.

Approach 3: Sort + Interleaving Variant (O(n log n) time, O(n) space)

Another interpretation splits the sorted array into two halves and interleaves smaller and larger elements. This guarantees the alternating inequality pattern by placing relatively larger values at odd indices and smaller ones at even indices. The idea appears in variations of wiggle problems where stricter ordering is required. For this specific problem it is usually unnecessary, but it helps illustrate how ordering constraints can be enforced structurally after sorting.

Recommended for interviews: The one-pass greedy approach is the expected solution. Interviewers want to see that you recognize the wiggle constraint can be enforced locally while iterating. Starting with the sorting approach shows clear reasoning, but the O(n) greedy pass demonstrates stronger algorithmic insight and better performance.