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
d1and next differenced2, 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 which will time out immediately on large inputs ().
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 . 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 time using constant space.
- Initialization: Start with
up = 1anddown = 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. - Iteration: Loop through the array starting from the second element (
i=1). Calculatediff = nums[i] - nums[i-1]. - 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 isdown + 1. The oldupvalue 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.
- If
- 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: where is the number of elements in
nums. We iterate through the list exactly once. - Space Complexity: . We only use two integer variables (
upanddown) 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.
upanddownremain 1. Returns 1. Correct. - Strictly Increasing Array
[1,2,3]:- Init:
up=1,down=1. - i=1 (
nums[1]=2 > nums[0]=1): Conditionnums[i] > nums[i-1]is true. Updateup = down + 1->up=2.downremains 1. - i=2 (
nums[2]=3 > nums[1]=2): Conditionnums[i] > nums[i-1]is true. Updateup = down + 1(wheredownis still 1) ->up=2. - Result:
max(2, 1)returns 2. Correct.
- Init:
- Strictly Decreasing Array: Symmetric to above logic; returns 2 for N>1.