376 - Wiggle Subsequence

Difficulty: Medium | Pattern: Greedy | Company tags: Google, Amazon

Problem Statement

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

• [1,7,4,9,2,5] is a wiggle sequence: differences are (6,-3,5,-7,3)
• [1,4,7,2,5] is NOT: differences (3,3,-5,3) have consecutive positives

Given an integer array nums, return the length of the longest wiggle subsequence.

Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6

Example 2:

Input: nums = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: e.g., [1,17,10,13,10,16,8]

Example 3:

Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2
Explanation: Only the first and last element.

Approach: Greedy — O(n), O(1)

Key insight: Greedily count direction changes. Track whether we need an "up" or "down" next. When consecutive elements in the same direction occur, ignore the interior ones — only the peak/valley matters.

Algorithm Flow

def wiggleMaxLength(nums: list[int]) -> int:
    if len(nums) < 2:
        return len(nums)
    
    up = 1   # length of longest wiggle ending with an upward movement
    down = 1 # length of longest wiggle ending with a downward movement
    
    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
        # equal: no change
    
    return max(up, down)

Dry Run

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

i	nums[i-1]	nums[i]	Direction	up	down
init				1	1
1	1	17	up	2	1
2	17	5	down	2	3
3	5	10	up	4	3
4	10	13	up	4	3
5	13	15	up	4	3
6	15	10	down	4	5
7	10	5	down	4	5
8	5	16	up	6	5
9	16	8	down	6	7

Result: max(6, 7) = 7 ✓

Why Equal Elements are Ignored

Equal adjacent elements don't contribute — they're not peaks or valleys and don't extend a wiggle sequence. The elif (not else) correctly skips them.

Edge Cases

• Single element → 1
• Two elements (equal) → 1
• Two elements (different) → 2
• All same → 1
• Alternating → n (whole array is wiggle)

Complexity

• Time: O(n)
• Space: O(1)

Key Terms

Term	Definition
Greedy	Making the locally optimal choice at each step without backtracking, trusting it leads to a global optimum.
Wiggle sequence	A sequence whose consecutive differences strictly alternate in sign (positive, negative, positive, ...).
Peak/valley	A local maximum or minimum element — the only points that can extend a wiggle sequence.
Two-state tracking	Maintaining separate running values (up, down) for "best sequence ending in an upward move" vs "ending in a downward move".

FAQ

Q: Why does the greedy approach work instead of needing full DP? A: Only direction changes (peaks and valleys) matter; monotonic runs collapse to their endpoints. Tracking up/down as the best wiggle length ending in each direction captures exactly this without needing to consider every subsequence.

Q: How does this relate to an O(n) DP formulation? A: The DP version defines up[i]/down[i] per index with the same transitions (up[i] = down[i-1]+1 if nums[i] > nums[i-1], similarly for down). The greedy code is just that DP compressed to O(1) space since only the previous state is needed.

Q: Can this be solved without extra space? A: Yes — the given solution already uses O(1) space with just two scalars, up and down.

Q: What if the array has all equal elements? A: Neither branch fires, so up and down stay at 1, correctly returning 1 (a single element is trivially the longest wiggle subsequence).

Q: How would you reconstruct the actual subsequence, not just its length? A: Track parent pointers or the actual indices chosen when updating up/down (or just record the sequence of direction changes as you scan), then backtrack from the larger of the two final states.

Quick Revision

• Goal: length of the longest subsequence with alternating strictly increasing/decreasing differences.
• Key insight: only peaks and valleys matter; flat/monotonic runs collapse.
• Track two running values: up (best ending on an upward move) and down (best ending on a downward move).
• On nums[i] > nums[i-1]: up = down + 1.
• On nums[i] < nums[i-1]: down = up + 1.
• On equal elements: no change (use elif, not else).
• Initialize both to 1 (a single element is a trivial wiggle sequence).
• Answer is max(up, down) at the end.
• Time: O(n), Space: O(1) — a greedy compression of an O(n) DP.

Related Problems

• 300 - Longest Increasing Subsequence — related sequence-DP problem also solvable greedily with optimization.
• 135 - Candy — another greedy problem driven by comparing adjacent elements and local peaks/valleys.
• Also related in pattern: "Best Time to Buy and Sell Stock II," which similarly exploits local peaks/valleys via a greedy scan.