Wiggle Sort

TARGET DECK: Leetcode FILE TAGS:

Intuition

• If you sort, the following property holds:
• You only have to consider every 2 indices.
• You know that x[0] $\le$ x[1]
• x[1] must be $\ge$ x[2]
• Therefore, greedily swap x[1] with x[2]
• Now, take note of the fact that x[1] is always $\le$ x[3] and onwards.
• Likewise, x[2] is always x[3] and onwards.
• Therefore, the problem reduces to swapping every 2 indices from the first index onwards.

Cards

START Basic Front: Wiggle Sort - LeetCode Back: Swap every 2 indices from first index onwards.

END

Complexity

Runtime

$O(NlogN)$

Space

$O(1)$

Code

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        n = len(nums)
        for i in range(1, n, 2):
            if i == n - 1:
                return
            nums[i], nums[i + 1] = nums[i + 1], nums[i]

Notes

---

References

Wiggle Sort - LeetCode