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

Item	Meaning
Input	An integer array nums
Output	Length of the longest wiggle subsequence
Constraint	1 <= nums.length <= 1000
Constraint	0 <= nums[i] <= 1000

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:

State	Meaning
up	Longest wiggle subsequence so far ending with an upward move
down	Longest wiggle subsequence so far ending with a downward move

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

Metric	Value	Why
Time	O(n)	We scan the array once
Space	O(1)	We keep only two counters

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:

Test	Why
[1, 7, 4, 9, 2, 5]	Already a full wiggle sequence
Long mixed example	Checks multiple turns
Strictly increasing array	Best answer is only 2
Single element	Minimum input size
Equal values	Zero differences must be ignored
Duplicates before a turn	Confirms equal values do not reset state
Plateau in the middle	Confirms repeated equal values are skipped