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, find the length of the longest subsequence where the differences between consecutive numbers strictly alternate between positive and negative. The sequence should follow an up-down or down-up pattern. You can delete elements but must preserve the original order.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
This approach tracks two states for every index: up[i] and down[i]. up[i] stores the length of the longest wiggle subsequence ending at index i where the last difference is positive, while down[i] stores the same when the last difference is negative. Iterate through the array once. If nums[i] > nums[i-1], update up[i] = down[i-1] + 1. If nums[i] < nums[i-1], update down[i] = up[i-1] + 1. Otherwise carry forward previous values. This works because a valid wiggle always extends the opposite direction state. The approach uses classic dynamic programming over an array, storing optimal subsequence lengths for each position.
Approach 2: Greedy Approach (O(n) time, O(1) space)
The optimal observation: only the direction of the last difference matters. You do not need to track full subsequences. Maintain two counters: up and down. Iterate through the array once. 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 valid wiggle. Each update represents extending a valid subsequence whose previous difference had the opposite sign. This works because only turning points (peaks and valleys) matter for maximizing wiggle length. The method is a classic greedy strategy that keeps only the best possible lengths without storing full DP arrays.
Recommended for interviews: The greedy solution is what most interviewers expect. It runs in O(n) time with O(1) space and shows you recognize the core insight: only direction changes matter. Explaining the dynamic programming version first can demonstrate understanding of state transitions, but converting it to the constant-space greedy form shows strong optimization skills.
In this approach, we maintain a greedy solution by keeping track of directions of the growing and shrinking sequences. We scan through the array, checking the differences between consecutive numbers. Whenever a change in the sign is detected, it contributes to a count of the longest wiggle sequence.
This approach efficiently computes in O(n) time by scanning the list only once.
The function wiggleMaxLength takes an array nums and its size. It uses two pointers up and down initialized as 1 representing the length of the longest subsequence. Loop through each element, and check if it's larger or smaller than the previous one, updating up and down appropriately. The final result is the maximum of these two values.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1).
This solution involves using dynamic programming to keep track of two arrays - up[i] and down[i] where up[i] and down[i] indicate the longest wiggle subsequence ending at index i with an upward or downward difference respectively.
This allows evaluating the longest wiggle subsequence leading to a time complexity of O(n^2), given we evaluate each index pair combination.
This approach makes use of two additional arrays up and down which are dynamically allocated to store the longest wiggle subsequence lengths. For each element, it checks all previous elements to update up and down arrays.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2).
Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n). |
| Dynamic Programming | Time Complexity: O(n^2). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n) | O(n) | When learning the state transitions or explaining the reasoning before optimization |
| Greedy | O(n) | O(1) | Best practical solution; minimal memory and expected in coding interviews |
Wiggle Subsequence | LeetCode | Explanation by alGOds! • alGOds • 9,233 views views
Watch 9 more video solutions →Practice Wiggle Subsequence with our built-in code editor and test cases.
Practice on FleetCode