Abstract / Summary

Find the longest subsequence where each pair of consecutive elements alternates between increasing and decreasing.

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 50% (600k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Greedy

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 presented implementation computes the length of the longest wiggle subsequence in a vector of integers. A wiggle subsequence alternates between increasing and decreasing differences. The algorithm maintains two associative containers, up and down, that map each distinct value to the length of the longest wiggle subsequence ending at that value with the last step being an upward or downward move respectively. By iterating through the input once and updating these maps with the help of ordered map operations, the method derives the global optimum without revisiting earlier elements.

Data Structures

Two ordered maps are declared:

map<int, int> up, down;

Each map stores a key-value pair where the key is a number from the input and the value is the best wiggle length that ends at that key with the appropriate direction. The ordered nature of std::map enables range queries based on value ordering, which the algorithm exploits to limit the amount of work needed for each element.

Initialization

Before processing the sequence, the algorithm ensures that every encountered number has an entry in both maps. The default length for a solitary element is one, reflecting a wiggle subsequence consisting of a single element.

if (up.count(n) == 0)
    up[n] = 1;
if (down.count(n) == 0)
    down[n] = 1;

This step guarantees that later look-ups never encounter missing keys, simplifying the update logic.

Main Processing Loop

The core of the algorithm iterates over each integer n in the input vector. For each n, two directional updates are performed.

Extending Downward Sequences

All entries in down whose keys are strictly less than n represent subsequences that end with a downward step and can be extended upward by appending n. The loop iterates from the beginning of down up to, but not including, the first element whose key is not less than n. For each such entry, the algorithm attempts to improve the up length for n.

for (auto i = down.begin(); i != down.lower_bound(n); i++)
    up[n] = max(up[n], i->second + 1);

Extending Upward Sequences

Conversely, entries in up whose keys are strictly greater than n can be extended downward by appending n. The loop starts at the first element with a key greater than n and proceeds to the end of the map, updating the down length for n.

for (auto i = up.upper_bound(n); i != up.end(); i++)
    down[n] = max(down[n], i->second + 1);

These two loops together explore all possible extensions that respect the wiggle direction, while the ordered map bounds keep the iteration focused on relevant candidates.

Result Aggregation

After processing all numbers, the algorithm scans both maps to locate the maximum length recorded. The final answer is the larger of the best upward and downward lengths.

int result = 0;
for (auto i : up)
    result = max(result, i.second);
for (auto i : down)
    result = max(result, i.second);
return result;

Because every possible subsequence terminates either with an upward or a downward step, the maximum across both maps represents the overall longest wiggle subsequence.

Edge Cases Handled

When the input vector is empty, the outer loop never executes, leaving both maps empty. The aggregation phase starts with result equal to zero, and the final return value is zero, correctly indicating that no wiggle subsequence exists.

If all elements are identical, each number receives an initial length of one, but no entry satisfies the strict inequality conditions required for extension. Consequently, the maps retain only the initial values, and the final result remains one, reflecting that a single element forms the longest possible wiggle subsequence in this scenario.

For strictly monotonic sequences (entirely increasing or decreasing), the algorithm progressively builds longer subsequences by repeatedly extending the opposite direction map. For an increasing series, each new element can extend a previously recorded downward subsequence, leading to a length that grows with the number of elements. The symmetric behavior holds for decreasing series, where upward extensions dominate.

Duplicate values are treated carefully: because the map keys are unique, repeated occurrences of the same number do not create separate entries. The initial insertion ensures a baseline length of one, and subsequent duplicates only attempt to improve the existing entry via the two directional loops. Since the loops use strict inequality (lower_bound for less-than and upper_bound for greater-than), equal values are excluded from extension, preserving the wiggle property that requires alternating strict differences.

Performance Optimizations

The use of ordered maps provides logarithmic access to keys and enables range queries (lower_bound and upper_bound) that restrict iteration to only those entries that can legitimately contribute to a wiggle extension. By avoiding a full scan of all previously seen values for each element, the algorithm reduces unnecessary work, especially when the input contains many distinct numbers.

Storing the best length per value rather than per index eliminates the need for an auxiliary array of size equal to the input length. This compact representation leverages the fact that only the relative ordering of values matters for wiggle extensions, allowing the algorithm to reuse previously computed results efficiently.

The final aggregation step iterates over each map exactly once, extracting the maximum without additional data structures. This straightforward pass complements the earlier incremental updates and ensures that the overall computation remains tight and focused.

Imagine a set of number blocks lined up in a row, all of different heights. The goal is to build a tall tower by picking blocks one by one, but with a special rule. If the last block placed was shorter than the one before it, the next block must be taller. If the last block placed was taller than the one before it, the next block must be shorter. This creates an alternating pattern that looks like a zig-zag.

The code uses two lists to keep track of how many blocks can fit into a sequence ending at a specific height. One list keeps track of sequences that end with an upward step, and the other keeps track of sequences that end with a downward step.

For every number found in the line, the computer checks all the previous possibilities. If it sees a block that is shorter than the current one, it tries to add this current block to a sequence that ended on a downward step to make a new upward step. If it sees a block that is taller than the current one, it tries to add this current block to a sequence that ended on an upward step to make a new downward step.

After looking at every block in the line, the computer peeks at all the completed sequences to find which one used the most blocks. The final answer is just the biggest number of blocks collected while following the zig-zag rule from start to finish.

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

Time: polynomial
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++	Python	Java				Go		TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	chenyanzhe	C++
	everthis				JS
	fpdjsns	C++
	halfrost							Go
	haoel	C++
	JoshCrozier				JS
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	martianoff					Scala
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM								C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fpdjsns	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
MacJim	C++
martianoff	Scala
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	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