LeetCode 376: Wiggle Subsequence

Problem Restatement

We are given an integer array nums.

A wiggle sequence is a sequence where the differences between neighboring numbers strictly alternate between positive and negative.

For example:

[1, 7, 4, 9, 2, 5]

The differences are:

[6, -3, 5, -7, 3]

The signs alternate:

positive, negative, positive, negative, positive

So this is a wiggle sequence.

We need to return the length of the longest wiggle subsequence.

A subsequence keeps the original order, but it may skip elements.

Input and Output

Example function shape:

def wiggleMaxLength(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 7, 4, 9, 2, 5]

The whole array already wiggles.

1 -> 7 goes up
7 -> 4 goes down
4 -> 9 goes up
9 -> 2 goes down
2 -> 5 goes up

So the answer is:

6

Example 2:

nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]

One longest wiggle subsequence is:

[1, 17, 10, 13, 10, 16, 8]

Its differences are:

[16, -7, 3, -3, 6, -8]

The signs alternate, so the answer is:

7

Example 3:

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]

This array only increases.

We can choose any two different numbers to make a wiggle sequence of length 2.

So the answer is:

2

First Thought: Dynamic Programming

A useful way to understand the problem is to keep two states.

For each position, we can ask:

If the current number is greater than the previous number, we can extend a sequence that previously ended with a downward move.

So:

up = down + 1

If the current number is smaller than the previous number, we can extend a sequence that previously ended with an upward move.

So:

down = up + 1

Equal adjacent values do not help, because a wiggle sequence requires non-zero differences.

Key Insight

We only care when the direction changes.

An increasing run like this:

[1, 2, 3, 4, 5]

does not give many wiggles. It gives only one upward move.

For the longest wiggle subsequence, we only need the turning points: local lows and local highs.

For example:

[1, 7, 4, 9, 2, 5]

Every step changes direction, so every number can be used.

But in:

[1, 2, 3, 4, 5]

there is no direction change, so the best length is only 2.

This leads to a greedy O(n) solution.

Algorithm

Initialize:

up = 1
down = 1

A single number is always a valid wiggle subsequence of length 1.

Then scan from left to right.

For each adjacent pair nums[i - 1] and nums[i]:

If nums[i] > nums[i - 1], the last move is upward, so update:

up = down + 1

If nums[i] < nums[i - 1], the last move is downward, so update:

down = up + 1

If they are equal, do nothing.

At the end, return:

max(up, down)

Correctness

The variables up and down store the best wiggle length seen so far with two possible last-move directions.

When we see an upward difference, the current number can only extend a subsequence whose last move was downward. This creates a valid alternation, so up = down + 1.

When we see a downward difference, the current number can only extend a subsequence whose last move was upward. This creates a valid alternation, so down = up + 1.

When the difference is zero, adding the current number would create a zero difference, which is not allowed in a wiggle sequence. So the best lengths stay unchanged.

The greedy update is safe because within a monotonic run, only the endpoint matters. Replacing an earlier value in that run with a later, more extreme value cannot reduce the chance of forming the next opposite move. Therefore counting direction changes gives the same length as the best subsequence.

Complexity

Implementation

class Solution:
    def wiggleMaxLength(self, nums: list[int]) -> int:
        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)

Code Explanation

We start both states at 1:

up = 1
down = 1

A single element is valid by itself.

Then we compare each number with the previous number:

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

If the current number is larger, the current step is an upward move:

if nums[i] > nums[i - 1]:
    up = down + 1

This means the best upward-ending wiggle sequence comes from a previous downward-ending sequence.

If the current number is smaller, the current step is a downward move:

elif nums[i] < nums[i - 1]:
    down = up + 1

Equal values are ignored because they produce a zero difference.

Finally:

return max(up, down)

The longest wiggle subsequence may end with either an upward move or a downward move.

Testing

def test_solution():
    s = Solution()

    assert s.wiggleMaxLength([1, 7, 4, 9, 2, 5]) == 6
    assert s.wiggleMaxLength([1, 17, 5, 10, 13, 15, 10, 5, 16, 8]) == 7
    assert s.wiggleMaxLength([1, 2, 3, 4, 5, 6, 7, 8, 9]) == 2
    assert s.wiggleMaxLength([5]) == 1
    assert s.wiggleMaxLength([0, 0]) == 1
    assert s.wiggleMaxLength([3, 3, 3, 2, 5]) == 3
    assert s.wiggleMaxLength([1, 2, 2, 2, 1]) == 3

    print("all tests passed")

test_solution()

Test meaning: