LeetCode 376 - Wiggle Subsequence

The problem asks us to find the length of the longest subsequence in an array such that the differences between consecutive elements alternate between positive and negative.

leetcodemediumarraydynamic-programminggreedy

LeetCode Problem 376

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem asks us to find the length of the longest subsequence in an array such that the differences between consecutive elements alternate between positive and negative.

A wiggle sequence follows a strict alternating pattern:

  • Positive difference, then negative difference, then positive again
  • Or negative difference, then positive difference, then negative again

The actual values do not matter as much as the direction of change between adjacent elements.

For example, the sequence [1, 7, 4, 9, 2, 5] has differences:

  • 7 - 1 = 6 → positive
  • 4 - 7 = -3 → negative
  • 9 - 4 = 5 → positive
  • 2 - 9 = -7 → negative
  • 5 - 2 = 3 → positive

Since the signs alternate perfectly, the entire sequence is a valid wiggle sequence.

The important detail is that we are looking for a subsequence, not necessarily a contiguous subarray. We are allowed to remove elements while preserving the original order.

The input is an integer array nums, and the output is a single integer representing the maximum possible length of a wiggle subsequence.

The constraints are:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Since the array length is at most 1000, even an O(n^2) dynamic programming solution would pass. However, the follow-up explicitly asks whether we can achieve O(n) time, which strongly suggests there is a greedy optimization.

Several edge cases are important:

  • Arrays with only one element should return 1
  • Arrays where all elements are equal should return 1
  • Strictly increasing or strictly decreasing arrays should return 2
  • Consecutive duplicate values must be ignored because a difference of zero is neither positive nor negative
  • Large alternating patterns should be handled efficiently without extra memory

Approaches

Brute Force Approach

A brute-force solution would generate every possible subsequence and check whether each one forms a valid wiggle sequence.

For each subsequence, we would compute consecutive differences and verify that their signs alternate strictly. We would then keep track of the maximum valid length.

This approach is correct because it exhaustively explores all possible subsequences. However, it is computationally infeasible because an array of length n has 2^n possible subsequences.

Even for n = 30, this becomes extremely large. Since the constraint allows up to 1000 elements, brute force is completely impractical.

Dynamic Programming Insight

The key observation is that we only care about the direction of the last difference.

At every position, we can maintain:

  • The longest wiggle subsequence ending with a positive difference
  • The longest wiggle subsequence ending with a negative difference

If the current number is larger than the previous one, we can extend a sequence that previously ended with a negative difference.

If the current number is smaller than the previous one, we can extend a sequence that previously ended with a positive difference.

This leads to a greedy optimization where we only track two values:

  • up → longest wiggle subsequence ending in an upward move
  • down → longest wiggle subsequence ending in a downward move

Because each element only depends on the previous state, we can solve the problem in linear time and constant space.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generates every subsequence and validates each
Optimal Greedy DP O(n) O(1) Tracks best upward and downward wiggle lengths

Algorithm Walkthrough

Optimal Greedy Dynamic Programming Algorithm

  1. Initialize two variables:
  • up = 1
  • down = 1

These represent the longest wiggle subsequence lengths ending in:

  • A positive difference
  • A negative difference

We start with 1 because a single element is trivially a wiggle sequence. 2. Iterate through the array starting from index 1. 3. Compare the current element with the previous element. 4. If nums[i] > nums[i - 1], we found a positive difference.

This means we can extend any sequence that previously ended with a negative difference.

Update:

up = down + 1
  1. If nums[i] < nums[i - 1], we found a negative difference.

This means we can extend any sequence that previously ended with a positive difference.

Update:

down = up + 1
  1. If the values are equal, do nothing.

Equal values produce a difference of zero, which does not contribute to a wiggle sequence. 7. Continue until the end of the array. 8. Return the maximum of up and down.

Why it works

The algorithm maintains an invariant:

  • up always stores the longest wiggle subsequence ending with a positive difference
  • down always stores the longest wiggle subsequence ending with a negative difference

Whenever we encounter a positive difference, the only valid extension is from a sequence ending in a negative difference. Similarly, a negative difference can only extend a sequence ending in a positive difference.

Because we only need the best lengths so far, we never need to store the actual subsequences. This allows the solution to run in constant space while still guaranteeing optimality.

Python Solution

from typing import List

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0

        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)

The implementation begins by handling the empty array case, although the problem guarantees at least one element.

The variables up and down both start at 1 because any single element forms a valid wiggle subsequence.

The loop processes adjacent pairs of elements. When the current element is larger than the previous one, we extend a downward sequence into an upward sequence. When the current element is smaller, we extend an upward sequence into a downward sequence.

Equal values are ignored because they do not contribute to alternation.

Finally, the algorithm returns the larger of the two states since the optimal sequence could end in either direction.

Go Solution

func wiggleMaxLength(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    up := 1
    down := 1

    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            up = down + 1
        } else if nums[i] < nums[i-1] {
            down = up + 1
        }
    }

    if up > down {
        return up
    }

    return down
}

The Go implementation follows the same logic as the Python solution.

Go does not have a built-in max function for integers, so the final comparison is done manually.

Slices in Go behave similarly to dynamic arrays, and integer overflow is not a concern because the maximum subsequence length is at most 1000.

Worked Examples

Example 1

Input:

nums = [1,7,4,9,2,5]
i nums[i-1] nums[i] Difference up down
Start - - - 1 1
1 1 7 Positive 2 1
2 7 4 Negative 2 3
3 4 9 Positive 4 3
4 9 2 Negative 4 5
5 2 5 Positive 6 5

Final answer:

6

The entire sequence forms a valid wiggle sequence.

Example 2

Input:

nums = [1,17,5,10,13,15,10,5,16,8]
i nums[i-1] nums[i] Difference up down
Start - - - 1 1
1 1 17 Positive 2 1
2 17 5 Negative 2 3
3 5 10 Positive 4 3
4 10 13 Positive 4 3
5 13 15 Positive 4 3
6 15 10 Negative 4 5
7 10 5 Negative 4 5
8 5 16 Positive 6 5
9 16 8 Negative 6 7

Final answer:

7

Example 3

Input:

nums = [1,2,3,4,5,6,7,8,9]
i nums[i-1] nums[i] Difference up down
Start - - - 1 1
1 1 2 Positive 2 1
2 2 3 Positive 2 1
3 3 4 Positive 2 1
4 4 5 Positive 2 1
5 5 6 Positive 2 1
6 6 7 Positive 2 1
7 7 8 Positive 2 1
8 8 9 Positive 2 1

Final answer:

2

Only two elements can form a valid wiggle sequence because the differences never alternate.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed exactly once
Space O(1) Only two integer variables are maintained

The algorithm performs a single pass through the array, making the runtime linear in the number of elements.

The space complexity is constant because no additional arrays or data structures are used. Regardless of input size, only the up and down variables are stored.

Test Cases

sol = Solution()

assert sol.wiggleMaxLength([1,7,4,9,2,5]) == 6  # classic alternating sequence
assert sol.wiggleMaxLength([1,17,5,10,13,15,10,5,16,8]) == 7  # mixed pattern
assert sol.wiggleMaxLength([1,2,3,4,5,6,7,8,9]) == 2  # strictly increasing
assert sol.wiggleMaxLength([9,8,7,6,5]) == 2  # strictly decreasing
assert sol.wiggleMaxLength([1]) == 1  # single element
assert sol.wiggleMaxLength([1,1,1,1]) == 1  # all duplicates
assert sol.wiggleMaxLength([1,2]) == 2  # two increasing elements
assert sol.wiggleMaxLength([2,1]) == 2  # two decreasing elements
assert sol.wiggleMaxLength([1,1,2]) == 2  # leading duplicates
assert sol.wiggleMaxLength([3,3,3,2,5]) == 3  # duplicates before valid wiggle
assert sol.wiggleMaxLength([1,7,7,7,4]) == 3  # repeated equal values in middle
assert sol.wiggleMaxLength([0,0]) == 1  # equal pair
assert sol.wiggleMaxLength([1,3,2,4,3,5]) == 6  # perfect alternation
assert sol.wiggleMaxLength([1,2,2,3,2]) == 3  # duplicates mixed with alternation

Test Summary

Test Why
[1,7,4,9,2,5] Standard alternating sequence
[1,17,5,10,13,15,10,5,16,8] Complex mixed pattern
[1,2,3,4,5,6,7,8,9] Strictly increasing case
[9,8,7,6,5] Strictly decreasing case
[1] Minimum input size
[1,1,1,1] All equal values
[1,2] Two-element increasing case
[2,1] Two-element decreasing case
[1,1,2] Leading duplicates
[3,3,3,2,5] Duplicate compression behavior
[1,7,7,7,4] Equal values inside sequence
[0,0] Equal adjacent pair
[1,3,2,4,3,5] Ideal wiggle pattern
[1,2,2,3,2] Alternation with duplicates

Edge Cases

All Elements Are Equal

An input like [5,5,5,5] is tricky because every difference is zero. A naive implementation might incorrectly count equal values as part of the wiggle sequence.

The correct answer is 1 because only a single element can form a valid wiggle sequence when no positive or negative differences exist.

The implementation handles this naturally by ignoring equal adjacent values.

Strictly Increasing or Decreasing Arrays

Arrays like [1,2,3,4,5] or [5,4,3,2,1] never alternate direction.

A common mistake is to count the entire sequence, but the longest valid wiggle subsequence only has length 2.

The algorithm correctly keeps either up or down fixed at 2 while the other remains 1.

Duplicate Values Between Direction Changes

Inputs like [1,7,7,7,4] can expose bugs if equal values are treated incorrectly.

The repeated 7s should not affect the wiggle structure because they produce zero differences.

The implementation ignores equal values entirely, ensuring duplicates neither increase nor reset the sequence length.