Wiggle Subsequence (LeetCode 376): Greedy Peak-Valley Count

You are given an integer array nums. A wiggle sequence is one where the differences between consecutive elements strictly alternate between positive and negative. Your job is to return the length of the longest wiggle subsequence.

This is LeetCode 376: Wiggle Subsequence, a medium problem that looks like it demands dynamic programming but has a clean greedy solution. The key insight is that you never need to look beyond local peaks and valleys. Once you see it, the solution fits in five lines.

What counts as a wiggle

A wiggle subsequence does not need to be contiguous. You can skip elements as long as the ones you keep alternate up-down-up-down (or down-up-down-up). Two or more consecutive rising differences are fine in the full array, but in your chosen subsequence, every adjacent pair must switch direction.

For example, given [1, 17, 5, 10, 13, 15, 10, 5, 16, 8], a valid wiggle of length 6 is [1, 17, 5, 15, 5, 16]. The runs of rises in the middle (5 to 10 to 13 to 15) can contribute at most one element to the subsequence. You just pick the highest point of that plateau.

The greedy approach

Instead of building the subsequence explicitly, you can count peaks and valleys as you scan left to right.

Here is the core idea. Track two values: up and down.

• up is the length of the longest wiggle subsequence ending with a rise.
• down is the length of the longest wiggle subsequence ending with a fall.

At each element, you compare it to the previous one:

• If nums[i] > nums[i-1], this is a rising step. You can extend any subsequence that last went down: up = down + 1.
• If nums[i] < nums[i-1], this is a falling step. You can extend any subsequence that last went up: down = up + 1.
• If they are equal, neither counter changes. Equal adjacent elements cannot be part of any wiggle.

At the end, the answer is max(up, down).

Why this works

The greedy argument is that you never benefit from skipping a local peak or valley. If there is a peak somewhere, including it can only help (or at worst be neutral). Skipping it cannot extend the sequence beyond what you would get by keeping it.

A consecutive run of rises like 5, 10, 13, 15 contributes exactly one peak no matter how long the run is. If up has already been updated during one of those earlier steps, the update at the next rising step produces the same value (up = down + 1 where down has not changed). That is why you see up stay constant during a monotonic run. The algorithm naturally "slides" the peak to the rightmost point of the run, which is optimal.

This is the peak-and-valley observation from the problem's editorial: the longest wiggle subsequence consists of all the alternating peaks and valleys of the array.

The code

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)
    up = 1
    down = 1
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up = down + 1
        elif nums[i] < nums[i - 1]:
            down = up + 1
    return max(up, down)

Let's walk through the logic:

1. If there is only one element, the answer is 1 by definition.
2. Both up and down start at 1. A single element trivially qualifies as a wiggle of length 1 ending with either direction.
3. For each pair of adjacent elements, apply the update rule. Equal elements get ignored.
4. Return the larger of the two counters.

Notice that up and down are always within 1 of each other. One counter only moves when the other does not, and it moves by exactly 1. This is the alternating nature of the wiggle encoded directly in the counters.

Complexity

One pass through the array. Two integer variables. There is no simpler way to do this because you must inspect every element at least once.

The building blocks

1. Greedy peak-valley counting

The pattern of scanning an array and greedily including each local extremum shows up across several problems. Once you learn to recognize "alternating direction" as the trigger for an update, you can apply the same counter-pair trick in related problems like Best Time to Buy and Sell Stock II, where you similarly count every up-move.

2. Running state pair

up and down are a pair of rolling state variables. Neither one is a "previous answer"; they each capture a different condition on the last element chosen. This is a generalization of the running-max trick from Maximum Subarray. Instead of one scalar, you track two because there are two ways for the subsequence to end.

3. DP alternative

There is also an O(n) DP solution. Define dp_up[i] as the longest wiggle ending at index i going up, and dp_down[i] going down. The recurrences are:

dp_up[i]   = max(dp_up[i-1],   dp_down[j] + 1) for all j < i where nums[i] > nums[j]
dp_down[i] = max(dp_down[i-1], dp_up[j] + 1)   for all j < i where nums[i] < nums[j]

The greedy solution is the O(1) space optimization of this. Instead of tracking all j, you only need to know the best dp_down seen so far when a rise occurs, and the best dp_up when a fall occurs. Those are exactly down and up in the greedy code.

Edge cases

Before submitting, check these:

• All same elements like [5, 5, 5]: no rising or falling steps, so up and down both stay at 1. Answer is 1.
• Two different elements like [3, 7]: one rising step, up = 2. Answer is 2.
• Two equal elements like [4, 4]: no update. Answer is 1.
• Already a perfect wiggle like [1, 7, 2, 8, 3]: every step alternates. Each step advances the relevant counter. Answer is n (the full array).
• Monotonically increasing like [1, 2, 3, 4]: only up advances, but only on the last step (since down never changes from 1). Answer is 2.

From understanding to recall

You have seen the solution and it makes sense. Two counters, alternating updates. But in an interview, details under pressure matter. Do you initialize both to 1 or 0? Do you return max(up, down) or just up? Do you handle the length-1 case explicitly?

These small details are exactly where people stumble when writing from memory. Spaced repetition is designed to close that gap. You practice writing the greedy counter update from scratch at increasing intervals until the initialization, the two branches, and the return are all automatic.

The peak-valley counting pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning each block individually and drilling it until the code flows without hesitation is far more efficient than grinding random problems and hoping they stick.

Related posts

• Jump Game - Another greedy single-pass problem where one rolling variable replaces a full DP table
• Maximum Subarray - Kadane's algorithm, the same "rolling state variable" idea applied to subarray sums
• Best Time to Buy and Sell Stock - Greedy running-max with a single variable, same family of O(n) O(1) solutions