Domain 2MediumCORE

Wiggle Subsequence

We are given an array of integers nums. We need to find the length of the longest subsequence where the differences between adjacent elements strictly alternate in sign (positive, then negative, or vice versa).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming#Greedy

376. Wiggle Subsequence

Model: qwen3.5:9b
Topics: Dynamic Programming,Greedy
FAANG asked: 0
Acceptance rate: 42.2%


Problem Breakdown

We are given an array of integers nums. We need to find the length of the longest subsequence where the differences between adjacent elements strictly alternate in sign (positive, then negative, or vice versa).

Key constraints and definitions:

  • Subsequence: Elements must maintain their original relative order.
  • Wiggle Condition: If we have a difference d1 and next difference d2, they cannot be both positive or both negative (and neither can be zero if it breaks the alternation). A sequence of length 0, 1 is trivially valid; length 2 requires non-zero diff.
  • Input: Array of integers (nums). Length between 1 and 1000. Values up to 1000.
  • Output: Integer representing the maximum count.

Implicit Edge Cases:

  • Single element input (handled by initialization).
  • All elements are identical (diff is always 0, result should be 1).
  • Strictly increasing or decreasing arrays (result should be 2 for N > 1).

Intuition

Initially, one might think of a brute-force approach: generate all possible subsequences and check if they are wiggle sequences. This is O(2n)O(2^n) which will time out immediately on large inputs (N=1000N=1000).

A dynamic programming solution where we track the longest subsequence ending at index i with an upward or downward slope seems viable, but that might suggest O(N2)O(N^2). However, notice a crucial property: We don’t need to know exactly which previous element formed the peak/valley. We only care about whether the last move was “up” or “down”.

If we have a sequence ending in an upward slope and encounter another number that is higher than the current one (another up), it doesn’t help us extend a wiggle. However, if we had previously ended with a downward slope, adding this new upward step extends our valid subsequence length by 1.

This suggests a greedy strategy: count every time the direction of change flips relative to the previous valid difference. Effectively, we are counting peaks and valleys in the array. We can maintain two state variables representing the longest wiggle sequence ending at current index with an upward slope (up) or downward slope (down).

Approach

We will use a greedy approach optimized into O(N)O(N) time using constant space.

  1. Initialization: Start with up = 1 and down = 1. These represent the length of the longest wiggle subsequence ending at index -1 (conceptually) or simply that we have counted the first element as a valid start point for both potential slopes.
  2. Iteration: Loop through the array starting from the second element (i=1). Calculate diff = nums[i] - nums[i-1].
  3. Logic Update:
    • If nums[i] > nums[i-1] (Up): We can extend a sequence that ended with a Down move to make it Up. So, the new length of an “up-ending” subsequence is down + 1. The old up value doesn’t change because we are ignoring consecutive ups for this specific state tracking logic; effectively, any previous up slope gets overwritten by the latest one that extends from a down move.
    • If nums[i] < nums[i-1] (Down): Similarly, extend an Up-ending sequence to make it Down: down = up + 1.
    • If equal (diff == 0): Ignore this step; neither state changes because we cannot wiggle with a zero difference.
  4. Result: After iterating through the array, one of our counters will hold the maximum length found (specifically, if the last move was up, up > down, and vice versa).

Complexity Analysis

  • Time Complexity: O(n)O(n) where nn is the number of elements in nums. We iterate through the list exactly once.
  • Space Complexity: O(1)O(1). We only use two integer variables (up and down) regardless of input size.

Solution

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)
    
    # up represents the length of longest subsequence ending with an upward slope
    # down represents the length of longest subsequence ending with a downward slope
    # Initialize both to 1 because we always have at least one element (the first one)
    up = 1 
    down = 1
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            # If current is greater than previous, extend the 'down' sequence to make it an 'up' move.
            # The length of up-ending sequences becomes (previous down count + 1).
            up = down + 1
        elif nums[i] < nums[i-1]:
            # If current is less than previous, extend the 'up' sequence to make it a 'down' move.
            # The length of down-ending sequences becomes (previous up count + 1).
            down = up + 1
            
    return max(up, down)

# Example usage:
print(wiggleMaxLength([1,7,4,9,2,5]))      # Output: 6
print(wiggleMaxLength([1,17,5,10,13,15,10,5,16,8])) # Output: 7

Edge Cases Handled

  • Single Element: The loop range(1, len(nums)) does not execute. Returns initial length (1). Correct.
  • All Elements Equal: Conditionals for greater/less are never met. up and down remain 1. Returns 1. Correct.
  • Strictly Increasing Array [1,2,3]:
    • Init: up=1, down=1.
    • i=1 (nums[1]=2 > nums[0]=1): Condition nums[i] > nums[i-1] is true. Update up = down + 1 -> up=2. down remains 1.
    • i=2 (nums[2]=3 > nums[1]=2): Condition nums[i] > nums[i-1] is true. Update up = down + 1 (where down is still 1) -> up=2.
    • Result: max(2, 1) returns 2. Correct.
  • Strictly Decreasing Array: Symmetric to above logic; returns 2 for N>1.