Wiggle Sort

Wiggle Sort

What is this problem about?

"Wiggle Sort" asks you to unsort an array into a specific "wiggle" pattern. For an input array, you need to reorder its elements in-place so that they follow the condition: nums[0] <= nums[1] >= nums[2] <= nums[3].... In other words, the elements should oscillate between small and large.

Why is this asked in interviews?

This problem is a great test of Greedy logic. While you could solve it by sorting the array first (O(N log N)), there is a more efficient O(N) solution that only requires a single pass. Interviewers at Google and Amazon use this to see if a candidate can find an optimal "one-pass" strategy instead of relying on the most obvious sorting-based approach.

Algorithmic pattern used

The pattern is a Greedy approach. You iterate through the array once. If the current index is even, you expect nums[i] <= nums[i+1]. If it's odd, you expect nums[i] >= nums[i+1]. If the condition isn't met, you simply swap the current element with the next one. This works because the swap doesn't break the wiggle property of the previous elements.

Example explanation

Array: [1, 5, 2, 4, 3].

1. Index 0 (even): 1 <= 5. OK.
2. Index 1 (odd): 5 >= 2. OK.
3. Index 2 (even): 2 <= 4. OK.
4. Index 3 (odd): 4 >= 3. OK. Result remains [1, 5, 2, 4, 3]. If it was [3, 5, 2, 1, 6, 4]:
5. Index 0 (even): 3 <= 5. OK.
6. Index 1 (odd): 5 >= 2. OK.
7. Index 2 (even): 2 <= 1. NO! Swap -> [3, 5, 1, 2, 6, 4].
8. Index 3 (odd): 2 >= 6. NO! Swap -> [3, 5, 1, 6, 2, 4]. ... and so on.

Common mistakes candidates make

• Sorting unnecessarily: Using O(N log N) when O(N) is possible.
• Complex swap logic: Thinking that a swap will ruin the "wiggle" established earlier. (In fact, the swap only improves or maintains the condition).
• Index out of bounds: Not stopping the loop at length - 1.

Interview preparation tip

For "wiggle" or "alternating" patterns, always check if a local swap is sufficient. Greedy solutions often work for these problems because each swap only needs to satisfy the immediate local constraint.