Abstract / Summary

Arrange numbers so that every even index is smaller than its neighbors and every odd index is larger than its neighbors.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Divide And Conquer
• Greedy
• Quickselect
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided wiggleSort method rearranges the elements of the input list nums so that they follow a wiggle pattern: every odd-indexed element is greater than its neighboring even-indexed elements. The algorithm works in-place, requiring no additional data structures beyond a temporary sorted copy of the original list.

Key Steps

1. Create a sorted copy of the input

s = sorted(nums)

The built-in sorted function returns a new list s containing the elements of nums in non-decreasing order. This step establishes a deterministic ordering from which the wiggle arrangement can be derived.

2. Initialise two pointers for the two halves

a = len(nums) - 1
b = a // 2

Pointer a starts at the last index of the sorted list, representing the largest elements. Pointer b starts at the middle index (rounded down), representing the median element and the smaller half of the sorted list. These pointers move inward as elements are placed back into nums.

3. Populate nums by alternating elements from the two halves

for i in range(len(s)):
    if i % 2 == 1:
        nums[i] = s[a]
        a -= 1
    else:
        nums[i] = s[b]
        b -= 1

The loop iterates over each position i in the original list. When i is odd, the algorithm assigns the current largest remaining element (s[a]) to nums[i] and decrements a. When i is even, it assigns the current smallest remaining element from the lower half (s[b]) and decrements b. This alternating placement guarantees that each odd index receives a value that is not smaller than its adjacent even indices.

Edge Cases Handled

When the input list is empty, sorted(nums) yields an empty list, a becomes -1, and the for loop executes zero times, leaving nums unchanged.

For a single-element list, a and b both resolve to 0. The loop runs once with i = 0 (even), assigning s[0] back to nums[0]. The list remains correctly ordered.

If the list contains duplicate values, the sorted copy preserves their relative order, and the alternating assignment still respects the wiggle condition because equal values can occupy adjacent positions without violating the “greater-than” requirement for odd indices.

When the length of nums is odd, the lower half contains one more element than the upper half. The pointer b starts one position left of the median, ensuring that the final even index receives the smallest remaining element, while the final odd index (if present) receives the largest remaining element from the upper half.

Performance Optimizations

The algorithm leverages Python’s highly optimized Timsort implementation via sorted, which adapts to existing order in the data and runs efficiently on real-world inputs. By constructing only a single auxiliary list s, the method avoids repeated allocations or costly data movements.

The two-pointer technique (a and b) enables constant-time element selection for each position in nums. Because the pointers move monotonically toward the start of the sorted list, no additional searches or index calculations are required inside the loop.

All assignments are performed directly into the original nums list, guaranteeing in-place modification without the overhead of creating a new result container. This approach minimizes memory pressure and improves cache locality, as the algorithm writes sequentially to nums while reading sequentially from s.

Overall, the combination of a single sort, two simple pointers, and direct in-place writes yields a concise and efficient solution for the wiggle sort problem.

Imagine a line of toys that are all mixed up and different sizes. This code works like a helper that organizes the toys into a special pattern where a small toy is followed by a big toy, then another small one, and then another big one.

First, the code sorts all the toys from the shortest to the tallest. It keeps the shorter half of the toys in one pile and the taller half in another pile.

Then, the code starts walking down the line of spots where the toys should go. When the spot is counted as an even number, it picks a toy from the pile of shorter toys to place there. When the spot is counted as an odd number, it picks a toy from the pile of taller toys. By doing this over and over, the code creates a line that wiggles up and down, making sure no two big toys are right next to each other.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++				Python	Java			TS
	WalkCCC	C++				Python	Java
	leetcode.ca	C++	JS			Python	Java	Go
	LeetcodeHelp	C++				Python	Java
	MemoryLimitExceeded	C++				Python
	Progiez	C++				Python	Java
github	black-shadows	C++
	charles-wangkai						Java
	chenyanzhe	C++
	everthis		JS
	FelixFan1122			C#
	halfrost							Go
	JoshCrozier		JS
	lkwq007					Python
	MacJim	C++
	ruoru				Rust
	suxrobGM			C#
	vli02								C
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
vli02	C
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality