Watch 10 video solutions for Wiggle Subsequence, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by alGOds has 9,233 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 one element and a sequence with two non-equal elements are trivially wiggle sequences.
[1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.[1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
Given an integer array nums, return the length of the longest wiggle subsequence of nums.
Example 1:
Input: nums = [1,7,4,9,2,5] Output: 6 Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
Example 2:
Input: nums = [1,17,5,10,13,15,10,5,16,8] Output: 7 Explanation: There are several subsequences that achieve this length. One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).
Example 3:
Input: nums = [1,2,3,4,5,6,7,8,9] Output: 2
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000
Follow up: Could you solve this in O(n) time?
Problem Overview: Given an integer array nums, find the length of the longest subsequence where the differences between consecutive numbers strictly alternate between positive and negative. The sequence is called a wiggle sequence. You do not need the elements to be contiguous, only in order.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
This method tracks two states for every index: up[i] and down[i]. up[i] stores the length of the longest wiggle subsequence ending at i with a positive difference, while down[i] stores the length ending with a negative difference. When nums[i] > nums[i-1], you extend a sequence that previously ended with a downward move: up[i] = down[i-1] + 1. When nums[i] < nums[i-1], you extend an upward sequence: down[i] = up[i-1] + 1. This approach models the alternating condition directly using dynamic programming. Time complexity is O(n) because you scan the array once, and space complexity is O(n) for the two DP arrays.
Approach 2: Greedy (O(n) time, O(1) space)
The greedy observation: only direction changes matter. You do not need to keep the entire subsequence—just track the best length ending with an upward or downward difference. Maintain two variables: up and down. If nums[i] > nums[i-1], update up = down + 1. If nums[i] < nums[i-1], update down = up + 1. Equal values are ignored because they do not create a wiggle. This works because replacing intermediate values with more extreme ones never hurts future alternation opportunities. The algorithm performs a single pass over the array, giving O(n) time and O(1) space. It is a classic example of simplifying a DP state transition using a greedy insight.
Recommended for interviews: Start by describing the DP formulation because it clearly models the alternating constraint and demonstrates reasoning about state transitions. Then optimize it to the greedy version by observing that only the previous direction matters. Interviewers typically expect the O(n) greedy solution with constant space, but showing the DP derivation proves you understand why the greedy rule works.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (up/down arrays) | O(n) | O(n) | When explaining the full state transition logic or learning the DP formulation |
| Greedy Optimization | O(n) | O(1) | Preferred in interviews and production when only the length is required |