# LeetCode 324: Wiggle Sort II

## Problem Restatement

We are given an integer array `nums`.

Rearrange it in-place so that:

```text
nums[0] < nums[1] > nums[2] < nums[3] ...
```

This alternating pattern is called wiggle order.

The official problem guarantees that a valid answer exists. The follow-up asks for `O(n)` average time and `O(1)` extra space. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0300-0399/0324.Wiggle%20Sort%20II/README_EN.md?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Rearrange `nums` in-place |
| Wiggle rule | `nums[0] < nums[1] > nums[2] < nums[3] ...` |
| Valid answer | Guaranteed to exist |

Function shape:

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

## Examples

Example 1:

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

One valid answer:

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

Check:

```text
1 < 6 > 1 < 5 > 1 < 4
```

Example 2:

```python
nums = [1, 3, 2, 2, 3, 1]
```

One valid answer:

```python
[2, 3, 1, 3, 1, 2]
```

Check:

```text
2 < 3 > 1 < 3 > 1 < 2
```

## First Thought: Sort and Alternate

A simple idea:

1. Sort the array.
2. Put small numbers at even indices.
3. Put large numbers at odd indices.

Example:

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

Odd positions should hold larger values:

```text
_ 6 _ 5 _ 4
```

Even positions hold smaller values:

```text
1 _ 1 _ 1 _
```

Result:

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

This works.

But we must be careful with duplicates.

A naive alternating fill can fail.

Example:

```python
[1, 1, 2, 2, 2, 2]
```

A careless arrangement may produce:

```text
1 < 2 > 2
```

which breaks strict inequality.

We need a more careful placement strategy.

## Key Insight

After sorting:

1. The smaller half should occupy even indices.
2. The larger half should occupy odd indices.
3. Fill both halves in reverse order.

Why reverse order?

Because duplicates should be separated as much as possible.

## Sorted Structure

Suppose:

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

Sorted:

```text
[1, 1, 1, 4, 5, 6]
```

Split:

| Half | Values |
|---|---|
| Small half | `[1,1,1]` |
| Large half | `[4,5,6]` |

Now place:

- Small half reversed into even indices.
- Large half reversed into odd indices.

Even positions:

```text
0, 2, 4
```

receive:

```text
1, 1, 1
```

Odd positions:

```text
1, 3, 5
```

receive:

```text
6, 5, 4
```

Result:

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

This guarantees:

```text
small < large > small < large
```

## Why Reverse Order Matters

Consider:

```python
nums = [1, 1, 2, 2, 2, 2]
```

Sorted:

```text
[1,1,2,2,2,2]
```

Small half:

```text
[1,1,2]
```

Large half:

```text
[2,2,2]
```

If we fill forward, duplicates can touch.

But reversing spreads equal values apart.

Result:

```python
[2, 2, 1, 2, 1, 2]
```

still has an issue at the beginning because equality appears immediately.

So the exact splitting matters:

```python
mid = (n + 1) // 2
```

The first half must contain the extra element when `n` is odd.

Then:

- Reverse-fill smaller half into even indices.
- Reverse-fill larger half into odd indices.

This arrangement prevents equal neighboring elements.

## Algorithm

1. Sort the array.
2. Split into:
   - smaller half
   - larger half
3. Reverse both halves.
4. Fill:
   - even indices from reversed smaller half
   - odd indices from reversed larger half

## Correctness

Let the sorted array be divided into:

- a smaller half `S`
- a larger half `L`

Every value in `S` is less than or equal to every value in `L`.

The algorithm places values from `S` into even indices and values from `L` into odd indices.

Odd indices are therefore filled with values at least as large as their neighboring even-index values.

The reverse placement is crucial. By filling both halves from largest to smallest, duplicate values from the same half are spread apart instead of clustered together. This prevents equal adjacent values from violating the strict wiggle inequalities.

For every odd index `i`:

```text
nums[i] > nums[i - 1]
```

because the odd position receives one of the largest remaining values from `L`, while the adjacent even position receives one of the largest remaining values from `S`, and all values in `L` are at least as large as those in `S`.

Similarly:

```text
nums[i] > nums[i + 1]
```

when `i + 1` exists.

Thus the final arrangement satisfies:

```text
nums[0] < nums[1] > nums[2] < nums[3] ...
```

## Complexity

Sorting dominates the complexity.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting |
| Space | `O(n)` | Temporary sorted copy |

The follow-up asks for `O(n)` average time and `O(1)` space using median partitioning and virtual indexing, but the sorting solution is much simpler and widely accepted in interviews.

## Implementation

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

        sorted_nums = sorted(nums)

        mid = (n + 1) // 2

        small = sorted_nums[:mid]
        large = sorted_nums[mid:]

        small.reverse()
        large.reverse()

        even = 0
        odd = 1

        for value in small:
            nums[even] = value
            even += 2

        for value in large:
            nums[odd] = value
            odd += 2
```

## Code Explanation

First sort the array.

```python
sorted_nums = sorted(nums)
```

Now split the array.

```python
mid = (n + 1) // 2
```

The smaller half gets the extra element when `n` is odd.

```python
small = sorted_nums[:mid]
large = sorted_nums[mid:]
```

Reverse both halves.

```python
small.reverse()
large.reverse()
```

This spreads duplicates apart.

Fill even indices using smaller values.

```python
even = 0

for value in small:
    nums[even] = value
    even += 2
```

Fill odd indices using larger values.

```python
odd = 1

for value in large:
    nums[odd] = value
    odd += 2
```

The final arrangement satisfies the wiggle condition.

## Follow-Up: O(n) Virtual Indexing Idea

The optimal follow-up solution uses:

1. Quickselect to find the median.
2. Three-way partitioning like Dutch National Flag.
3. Virtual indexing.

Virtual index mapping:

```python
(1 + 2 * i) % (n | 1)
```

This remaps positions so large values naturally move to odd indices.

That solution achieves:

| Metric | Value |
|---|---:|
| Time | `O(n)` average |
| Space | `O(1)` |

But it is substantially harder to implement correctly.

## Testing

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

    return True

def run_tests():
    s = Solution()

    nums1 = [1, 5, 1, 1, 6, 4]
    s.wiggleSort(nums1)
    assert is_wiggle(nums1)

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

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

    nums4 = [4, 5, 5, 6]
    s.wiggleSort(nums4)
    assert is_wiggle(nums4)

    nums5 = [1]
    s.wiggleSort(nums5)
    assert nums5 == [1]

    nums6 = [2, 2]
    s.wiggleSort(nums6)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Basic correctness |
| Duplicates | Strict inequality handling |
| Many repeated values | Hard duplicate arrangement |
| Small even array | Boundary case |
| Single element | Smallest input |
| Two equal values | Edge condition outside strict feasibility assumptions |