LeetCode 280 - Wiggle Sort

The problem asks us to rearrange an integer array so that it follows a specific alternating pattern called a wiggle sequence. The required relationship is: - nums[0] <= nums[1] - nums[1] = nums[2] - nums[2] <= nums[3] - nums[3] = nums[4] - and so on.

leetcodemediumarraygreedysorting

LeetCode Problem 280

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to rearrange an integer array so that it follows a specific alternating pattern called a wiggle sequence.

The required relationship is:

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

In other words, the values should alternate between valleys and peaks. Elements at odd indices should be greater than or equal to their neighbors, while elements at even indices should be less than or equal to their neighbors.

The input is a single integer array nums, and the task is to modify the array in place. We are not asked to return a new array.

The constraints are important:

  • The array length can be as large as 5 * 10^4
  • Values range from 0 to 10^4
  • The problem guarantees that at least one valid wiggle arrangement always exists

Because the input can be fairly large, an O(n^2) solution would be inefficient. The follow-up explicitly asks whether the problem can be solved in linear time, which strongly hints that a greedy or single-pass approach exists.

Several edge cases are important to think about early:

  • Arrays with only one element are already valid
  • Arrays with duplicate values must still satisfy non-strict inequalities
  • Already wiggle-sorted arrays should remain valid
  • Strictly increasing or strictly decreasing arrays require multiple swaps
  • Adjacent equal values can easily break incorrect implementations if strict comparisons are used instead of non-strict comparisons

The guarantee that a valid answer always exists simplifies the problem because we do not need to detect impossible configurations.

Approaches

Brute Force Approach

A straightforward idea is to sort the array first and then rearrange elements into alternating low and high positions.

One possible implementation is:

  1. Sort the array
  2. Interleave smaller and larger halves
  3. Place values into alternating positions

Sorting makes it easier to control ordering relationships because the numbers are already arranged globally. After sorting, we can intentionally place elements so the wiggle condition holds.

This works because sorted order gives enough structure to ensure alternating peaks and valleys. However, sorting requires O(n log n) time, which is slower than the optimal linear-time solution requested in the follow-up.

The approach is acceptable for the given constraints, but it is not optimal.

Optimal Greedy Approach

The key observation is that we do not need the entire array globally sorted. We only need every adjacent pair to satisfy a local condition.

For every index:

  • If the index is odd, we need nums[i] >= nums[i - 1]
  • If the index is even, we need nums[i] <= nums[i - 1]

If the condition is violated, swapping the two adjacent elements immediately fixes that local relationship.

The important insight is that fixing one pair greedily does not destroy the validity of previous pairs. Because each swap only involves adjacent elements, earlier wiggle relationships remain correct.

This allows us to solve the problem in a single left-to-right pass.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(1) or O(n) Sort first, then rearrange into wiggle order
Optimal O(n) O(1) Single-pass greedy swapping based on local violations

Algorithm Walkthrough

Optimal Greedy Algorithm

  1. Iterate through the array starting from index 1.

At every step, we examine the relationship between nums[i] and nums[i - 1]. 2. If the current index is odd, ensure that the current element is greater than or equal to the previous element.

The required condition is:

nums[i] >= nums[i - 1]

If this condition is violated, swap the two elements. 3. If the current index is even, ensure that the current element is less than or equal to the previous element.

The required condition is:

nums[i] <= nums[i - 1]

If this condition is violated, swap the two elements. 4. Continue this process until the end of the array.

Each step fixes the wiggle relationship for the current adjacent pair.

Why it works

The algorithm maintains the invariant that all positions before index i already satisfy the wiggle condition.

When processing index i, only the relationship between nums[i - 1] and nums[i] may be invalid. If we swap them, the current pair becomes valid without breaking earlier pairs.

This works because the swap only changes the ordering of two adjacent elements, and the previous relationships remain compatible with the wiggle constraints.

By the end of the traversal, every adjacent pair satisfies the required alternating inequality pattern.

Python Solution

from typing import List

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        for i in range(1, len(nums)):
            
            # Odd index should be a peak
            if i % 2 == 1:
                if nums[i] < nums[i - 1]:
                    nums[i], nums[i - 1] = nums[i - 1], nums[i]
            
            # Even index should be a valley
            else:
                if nums[i] > nums[i - 1]:
                    nums[i], nums[i - 1] = nums[i - 1], nums[i]

The implementation follows the greedy strategy exactly.

The loop starts from index 1 because every comparison involves the previous element.

For odd indices, the current value must be greater than or equal to the previous value. If not, the two elements are swapped.

For even indices, the current value must be less than or equal to the previous value. Again, if the condition is violated, a swap fixes it immediately.

The algorithm modifies the array in place, which satisfies the problem requirements and keeps space usage constant.

Go Solution

func wiggleSort(nums []int) {
    
    for i := 1; i < len(nums); i++ {
        
        // Odd index should be a peak
        if i%2 == 1 {
            if nums[i] < nums[i-1] {
                nums[i], nums[i-1] = nums[i-1], nums[i]
            }
        } else {
            // Even index should be a valley
            if nums[i] > nums[i-1] {
                nums[i], nums[i-1] = nums[i-1], nums[i]
            }
        }
    }
}

The Go implementation mirrors the Python logic closely.

Go slices are reference-like structures, so modifications inside the function affect the original array directly. No additional memory allocation is required.

Unlike Python, Go does not require explicit type hints because the slice type is already specified in the function signature.

There are no integer overflow concerns because the algorithm only compares and swaps values.

Worked Examples

Example 1

Input:

nums = [3,5,2,1,6,4]

We process the array from left to right.

Index Expected Relation Current Pair Action Array State
1 nums[1] >= nums[0] 5 >= 3 No swap [3,5,2,1,6,4]
2 nums[2] <= nums[1] 2 <= 5 No swap [3,5,2,1,6,4]
3 nums[3] >= nums[2] 1 >= 2 is false Swap [3,5,1,2,6,4]
4 nums[4] <= nums[3] 6 <= 2 is false Swap [3,5,1,6,2,4]
5 nums[5] >= nums[4] 4 >= 2 No swap [3,5,1,6,2,4]

Final result:

[3,5,1,6,2,4]

This satisfies:

3 <= 5 >= 1 <= 6 >= 2 <= 4

Example 2

Input:

nums = [6,6,5,6,3,8]
Index Expected Relation Current Pair Action Array State
1 nums[1] >= nums[0] 6 >= 6 No swap [6,6,5,6,3,8]
2 nums[2] <= nums[1] 5 <= 6 No swap [6,6,5,6,3,8]
3 nums[3] >= nums[2] 6 >= 5 No swap [6,6,5,6,3,8]
4 nums[4] <= nums[3] 3 <= 6 No swap [6,6,5,6,3,8]
5 nums[5] >= nums[4] 8 >= 3 No swap [6,6,5,6,3,8]

The array already satisfies the wiggle condition, so no swaps are needed.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array
Space O(1) Only a few temporary variables are used

The algorithm visits each element exactly once and performs at most one swap per index. Since all operations inside the loop are constant time, the total runtime is linear.

The algorithm modifies the array in place and does not allocate any additional data structures proportional to input size, so the space complexity is constant.

Test Cases

from typing import List

def is_wiggle(nums: List[int]) -> bool:
    for i in range(1, len(nums)):
        if i % 2 == 1:
            if nums[i] < nums[i - 1]:
                return False
        else:
            if nums[i] > nums[i - 1]:
                return False
    return True

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        for i in range(1, len(nums)):
            if i % 2 == 1:
                if nums[i] < nums[i - 1]:
                    nums[i], nums[i - 1] = nums[i - 1], nums[i]
            else:
                if nums[i] > nums[i - 1]:
                    nums[i], nums[i - 1] = nums[i - 1], nums[i]

sol = Solution()

# Example 1
nums = [3, 5, 2, 1, 6, 4]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # standard unsorted example

# Example 2
nums = [6, 6, 5, 6, 3, 8]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # duplicates already valid

# Single element
nums = [1]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # minimum size input

# Two increasing elements
nums = [1, 2]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # simple valid pair

# Two decreasing elements
nums = [2, 1]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # requires one swap

# Strictly increasing
nums = [1, 2, 3, 4, 5, 6]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # many local fixes needed

# Strictly decreasing
nums = [6, 5, 4, 3, 2, 1]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # alternating swaps required

# All equal values
nums = [4, 4, 4, 4]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # equality handling

# Repeated alternating values
nums = [1, 3, 1, 3, 1, 3]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # already perfect wiggle

# Random mixed case
nums = [9, 1, 8, 2, 7, 3, 6]
sol.wiggleSort(nums)
assert is_wiggle(nums)  # mixed ordering

Test Case Summary

Test Why
[3,5,2,1,6,4] Standard example with multiple swaps
[6,6,5,6,3,8] Duplicate values and already valid
[1] Minimum input size
[1,2] Small increasing array
[2,1] Small decreasing array
[1,2,3,4,5,6] Strictly increasing sequence
[6,5,4,3,2,1] Strictly decreasing sequence
[4,4,4,4] Equality edge case
[1,3,1,3,1,3] Already wiggle-sorted input
[9,1,8,2,7,3,6] General mixed ordering

Edge Cases

Single Element Array

An array containing only one element is automatically wiggle-sorted because there are no adjacent relationships to validate.

This case can cause issues in implementations that assume at least two elements exist. The current implementation handles it naturally because the loop starts at index 1, so no iterations occur.

Duplicate Values

Arrays with repeated values are important because the condition uses non-strict inequalities.

For example:

[4,4,4,4]

is already valid because:

4 <= 4 >= 4 <= 4

A common bug is using strict < and > comparisons incorrectly, which would force unnecessary swaps or incorrectly reject valid states.

The implementation correctly uses non-strict logic by swapping only when the required inequality is violated.

Strictly Increasing or Decreasing Arrays

Inputs like:

[1,2,3,4,5,6]

or

[6,5,4,3,2,1]

require multiple local corrections.

Naive approaches may try to globally rearrange elements, but the greedy algorithm handles these efficiently through adjacent swaps.

Each iteration fixes exactly one local violation, and because previous positions remain valid, the algorithm converges in a single pass.