Problem Description

Given an integer array nums, you need to reorder it to follow a "wiggle" pattern where:

• nums[0] <= nums[1] >= nums[2] <= nums[3] >= nums[4]...

In other words:

• Elements at even indices (0, 2, 4, ...) should be less than or equal to their next neighbor
• Elements at odd indices (1, 3, 5, ...) should be greater than or equal to their next neighbor

This creates an alternating pattern where the values go up, then down, then up, then down, like a wiggle.

For example:

• Input: [3, 5, 2, 1, 6, 4]
• One valid output: [3, 5, 1, 6, 2, 4]
  • Position 0: 3 <= 5 ✓
  • Position 1: 5 >= 1 ✓
  • Position 2: 1 <= 6 ✓
  • Position 3: 6 >= 2 ✓
  • Position 4: 2 <= 4 ✓

The problem guarantees that the input array will always have at least one valid answer. You need to modify the array in-place without returning anything.

Intuition

The key insight is that we don't need to sort the entire array to achieve the wiggle pattern. Instead, we can fix violations locally as we traverse the array.

Think about what makes a valid wiggle sort: at each position, we only care about the relationship between the current element and its immediate neighbor. If we're at an odd index, the current element should be greater than or equal to the previous one. If we're at an even index, the current element should be less than or equal to the previous one.

When we encounter a violation of this rule, we can simply swap the current element with the previous one. Why does this work?

Consider two cases:

1. At odd index i, if nums[i] < nums[i-1] (violation), swapping them makes nums[i] >= nums[i-1]. This swap won't break the relationship at i-1 because:

   • At i-1 (even index), we needed nums[i-1] <= nums[i-2]
   • After swap, the smaller value moves to i-1, so nums[i-1] <= nums[i-2] still holds

2. At even index i, if nums[i] > nums[i-1] (violation), swapping them makes nums[i] <= nums[i-1]. Similarly, this maintains the validity at position i-1.

The beauty of this approach is its greediness - we make local corrections that guarantee global correctness. Each swap fixes the current position without breaking previous positions, allowing us to solve the problem in a single pass with O(n) time and O(1) space.

Solution Approach

The implementation uses a single-pass greedy algorithm to create the wiggle pattern. Here's how it works:

We iterate through the array starting from index 1, checking each element against its predecessor. At each position i, we determine whether a swap is needed based on two conditions:

1. Odd index condition: If i is odd (1, 3, 5, ...), we need nums[i] >= nums[i-1]. If nums[i] < nums[i-1], we swap them.

2. Even index condition: If i is even (2, 4, 6, ...), we need nums[i] <= nums[i-1]. If nums[i] > nums[i-1], we swap them.

The code combines these conditions into a single if statement:

if (i % 2 == 1 and nums[i] < nums[i - 1]) or (i % 2 == 0 and nums[i] > nums[i - 1]):
    nums[i], nums[i - 1] = nums[i - 1], nums[i]

Let's trace through an example with nums = [3, 5, 2, 1, 6, 4]:

• i = 1 (odd): Compare 5 with 3. Since 5 >= 3, no swap needed. Array: [3, 5, 2, 1, 6, 4]
• i = 2 (even): Compare 2 with 5. Since 2 < 5, no swap needed. Array: [3, 5, 2, 1, 6, 4]
• i = 3 (odd): Compare 1 with 2. Since 1 < 2, swap them. Array: [3, 5, 1, 2, 6, 4]
• i = 4 (even): Compare 6 with 2. Since 6 > 2, swap them. Array: [3, 5, 1, 6, 2, 4]
• i = 5 (odd): Compare 4 with 2. Since 4 > 2, no swap needed. Final: [3, 5, 1, 6, 2, 4]

The algorithm modifies the array in-place with O(n) time complexity and O(1) space complexity, making it highly efficient.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the array [6, 3, 4, 2].

Initial array: [6, 3, 4, 2]

We want to achieve the wiggle pattern: nums[0] <= nums[1] >= nums[2] <= nums[3]...

Step 1: i = 1 (odd index)

• We need nums[1] >= nums[0]
• Check: 3 >= 6? No, 3 < 6 (violation!)
• Action: Swap nums[1] and nums[0]
• Array becomes: [3, 6, 4, 2]

Step 2: i = 2 (even index)

• We need nums[2] <= nums[1]
• Check: 4 <= 6? Yes (no violation)
• Action: No swap needed
• Array remains: [3, 6, 4, 2]

Step 3: i = 3 (odd index)

• We need nums[3] >= nums[2]
• Check: 2 >= 4? No, 2 < 4 (violation!)
• Action: Swap nums[3] and nums[2]
• Array becomes: [3, 6, 2, 4]

Final result: [3, 6, 2, 4]

Let's verify the wiggle pattern:

• Position 0: 3 <= 6 ✓
• Position 1: 6 >= 2 ✓
• Position 2: 2 <= 4 ✓

The key insight is that each swap fixes the current position's violation while preserving the correctness of previous positions. When we swap at an odd index, we move the larger value to that position (satisfying the >= requirement), and the smaller value goes to the previous even position (which needed a <= relationship). This greedy approach guarantees we achieve a valid wiggle pattern in just one pass through the array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums. The algorithm makes a single pass through the array starting from index 1, performing constant-time operations (comparison and swap) at each position. Each element is visited exactly once, resulting in linear time complexity.

Space Complexity: O(1). The algorithm modifies the array in-place and only uses a constant amount of extra space for the loop variable i and temporary variables during the swap operation. No additional data structures are created that depend on the input size.

Common Pitfalls

Pitfall 1: Confusing Index Positions with Element Values

A common mistake is misunderstanding which indices should be "peaks" and which should be "valleys" in the wiggle pattern. Developers often incorrectly assume:

• Even indices (0, 2, 4, ...) should be greater than their neighbors
• Odd indices (1, 3, 5, ...) should be less than their neighbors

This is backwards! The correct pattern is:

• Even indices are valleys: nums[even] <= nums[even+1]
• Odd indices are peaks: nums[odd] >= nums[odd+1]

Wrong Implementation:

# Incorrect: Swapped the conditions
if (i % 2 == 0 and nums[i] < nums[i - 1]) or \
   (i % 2 == 1 and nums[i] > nums[i - 1]):
    nums[i], nums[i - 1] = nums[i - 1], nums[i]

Solution: Remember that odd indices should be local maxima (peaks) and even indices should be local minima (valleys) when considering non-zero based indexing.

Pitfall 2: Overthinking with Sorting

Many developers initially approach this problem by sorting the array first, then trying to rearrange elements in a complex manner:

Overcomplicated Approach:

def wiggleSort(self, nums: List[int]) -> None:
    sorted_nums = sorted(nums)
    # Try to interleave small and large elements
    for i in range(len(nums)):
        if i % 2 == 0:
            nums[i] = sorted_nums[i // 2]
        else:
            nums[i] = sorted_nums[len(nums) // 2 + i // 2]

This approach is unnecessarily complex and has O(n log n) time complexity due to sorting.

Solution: Trust the greedy approach. The single-pass algorithm with local swaps is sufficient and optimal at O(n) time complexity.

Pitfall 3: Attempting to Maintain Global Ordering

Some developers try to ensure that all elements at odd indices are globally larger than elements at even indices, which is NOT required:

Incorrect Assumption:

# Wrong: Trying to ensure all odd-index elements > all even-index elements
def wiggleSort(self, nums: List[int]) -> None:
    nums.sort()
    mid = len(nums) // 2
    # Trying to separate into "small" and "large" groups
    result = []
    for i in range(mid):
        result.append(nums[i])
        if mid + i < len(nums):
            result.append(nums[mid + i])
    nums[:] = result

Solution: The wiggle pattern only requires local relationships between adjacent elements, not global ordering. An element at an odd index only needs to be >= its immediate neighbors, not all elements at even indices.

Pitfall 4: Forgetting Edge Cases with Small Arrays

Developers sometimes forget to handle arrays with only 1 or 2 elements properly:

Potential Issue:

def wiggleSort(self, nums: List[int]) -> None:
    # Might cause issues if not careful with bounds
    for i in range(len(nums)):  # Starting from 0 instead of 1
        if i % 2 == 1 and nums[i] < nums[i - 1]:  # i-1 could be -1
            nums[i], nums[i - 1] = nums[i - 1], nums[i]

Solution: Always start the iteration from index 1 (as in the correct solution) since we're comparing with the previous element. Arrays with length 1 are already valid wiggle arrays.