# LeetCode 280: Wiggle Sort

## Problem Restatement

We are given an unsorted integer array `nums`.

We need to reorder it in-place so that it follows this pattern:

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

So the values should alternate between low and high.

The problem asks us to modify `nums` directly and return nothing. The input is guaranteed to have at least one valid answer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Nothing |
| Mutation | Reorder `nums` in-place |
| Pattern | `nums[0] <= nums[1] >= nums[2] <= nums[3] ...` |

Function shape:

```python
class Solution:
    def wiggleSort(self, nums: list[int]) -> None:
        ...
```

## Examples

For:

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

One valid output is:

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

Check the pattern:

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

Another valid output could also be accepted. The problem only requires the array to satisfy the wiggle pattern.

For:

```python
nums = [6, 6, 5, 6, 3, 8]
```

The array already satisfies:

```python
6 <= 6 >= 5 <= 6 >= 3 <= 8
```

So it may remain unchanged.

## First Thought: Sort First

A simple idea is to sort the array first.

For example:

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

After sorting:

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

Then we can swap each adjacent pair starting from index `1`:

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

This satisfies:

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

Code:

```python
class Solution:
    def wiggleSort(self, nums: list[int]) -> None:
        nums.sort()

        for i in range(1, len(nums) - 1, 2):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
```

This works, but sorting costs `O(n log n)`.

The follow-up asks whether we can solve it in `O(n)` time.

## Key Insight

We only need each neighboring pair to satisfy the local rule.

For index `i`, compare `nums[i]` with `nums[i - 1]`.

If `i` is odd, then `nums[i]` should be greater than or equal to `nums[i - 1]`.

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

If `i` is even, then `nums[i]` should be less than or equal to `nums[i - 1]`.

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

Whenever this local rule is violated, we swap the two adjacent elements.

That single swap fixes the relationship at position `i - 1` and `i`.

## Algorithm

Scan from left to right, starting at index `1`.

For each index `i`:

If `i` is odd, we need:

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

If this is false, swap them.

If `i` is even, we need:

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

If this is false, swap them.

After the scan finishes, the whole array satisfies the wiggle condition.

## Correctness

We prove that after processing index `i`, the prefix `nums[0:i+1]` satisfies the required wiggle pattern.

For `i = 1`, the algorithm checks whether `nums[0] <= nums[1]`. If the condition fails, it swaps the two values, so the condition becomes true.

Now assume the prefix ending at `i - 1` already satisfies the pattern.

When processing index `i`, the algorithm only checks the relationship between `nums[i - 1]` and `nums[i]`.

If `i` is odd, it ensures:

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

If `i` is even, it ensures:

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

If no swap is needed, the prefix remains valid.

If a swap is needed, the new value placed at `i - 1` still preserves the previous relationship with `nums[i - 2]`.

For an odd `i`, the violation means `nums[i] < nums[i - 1]`. Swapping places the smaller value at even index `i - 1`, which can only help the previous `<=` valley relation.

For an even `i`, the violation means `nums[i] > nums[i - 1]`. Swapping places the larger value at odd index `i - 1`, which can only help the previous `>=` peak relation.

So the previous prefix remains valid, and the new adjacent pair becomes valid.

By induction, after the last index is processed, the entire array satisfies the wiggle pattern.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We only swap elements in-place |

## Implementation

```python
class Solution:
    def wiggleSort(self, nums: list[int]) -> None:
        for i in range(1, len(nums)):
            should_be_peak = i % 2 == 1

            if should_be_peak and nums[i] < nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

            if not should_be_peak and nums[i] > nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]
```

## Code Explanation

We start from index `1` because every rule compares the current element with the previous one:

```python
for i in range(1, len(nums)):
```

Odd indices should be peaks:

```python
should_be_peak = i % 2 == 1
```

If `i` is odd but `nums[i]` is smaller than the previous value, the peak rule is violated:

```python
if should_be_peak and nums[i] < nums[i - 1]:
    nums[i], nums[i - 1] = nums[i - 1], nums[i]
```

If `i` is even but `nums[i]` is larger than the previous value, the valley rule is violated:

```python
if not should_be_peak and nums[i] > nums[i - 1]:
    nums[i], nums[i - 1] = nums[i - 1], nums[i]
```

The function returns nothing because the array is modified in-place.

## Testing

```python
def is_wiggle(nums):
    for i in range(len(nums) - 1):
        if i % 2 == 0:
            if nums[i] > nums[i + 1]:
                return False
        else:
            if nums[i] < nums[i + 1]:
                return False

    return True

def test_wiggle_sort():
    s = Solution()

    nums = [3, 5, 2, 1, 6, 4]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    nums = [6, 6, 5, 6, 3, 8]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    nums = [1]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    nums = [2, 1]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    nums = [1, 1, 1, 1]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    print("all tests passed")

test_wiggle_sort()
```

Test meaning:

| Test | Why |
|---|---|
| `[3, 5, 2, 1, 6, 4]` | Standard example |
| `[6, 6, 5, 6, 3, 8]` | Already valid with duplicates |
| `[1]` | Smallest array |
| `[2, 1]` | Needs one swap |
| `[1, 1, 1, 1]` | Equality is allowed |