Wiggle Subsequence
MedPrompt
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.
- For example,
[1, 7, 4, 9, 2, 5]is a wiggle sequence because the differences(6, -3, 5, -7, 3)alternate between positive and negative. - In contrast,
[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?
Approaches
2 approaches with complexity analysis and trade-offs.
This problem has optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. We can define the state based on the length of the wiggle subsequence ending at each index. However, to correctly build the sequence, we also need to know the direction of the last wiggle (up or down). Therefore, we use two DP arrays: one for subsequences ending with an upward wiggle (up) and one for those ending with a downward wiggle (down).
Algorithm
- Create two integer arrays,
upanddown, of the same size as the input arraynums. up[i]will store the length of the longest wiggle subsequence ending at indexiwith a positive difference (an "up" wiggle).down[i]will store the length of the longest wiggle subsequence ending at indexiwith a negative difference (a "down" wiggle).- Initialize all elements of
upanddownto 1, as any single element is a wiggle subsequence of length 1. - Iterate through the array
numswith an outer loop fromi = 1ton-1. - Inside, have an inner loop from
j = 0toi-1. - If
nums[i] > nums[j], it means we can potentially extend a "down" wiggle ending atj. Updateup[i] = max(up[i], down[j] + 1). - If
nums[i] < nums[j], it means we can potentially extend an "up" wiggle ending atj. Updatedown[i] = max(down[i], up[j] + 1). - After the loops complete, the length of the longest wiggle subsequence is the maximum value found in either the
upordownarray. - Handle the edge case of an empty or single-element array separately; the length is simply the number of elements.
Walkthrough
We define up[i] as the length of the longest wiggle subsequence of nums[0...i] ending at nums[i], where the last difference is positive. Similarly, down[i] is the length of the longest wiggle subsequence ending at nums[i] where the last difference is negative.
To compute up[i], we look at all previous elements nums[j] (where j < i). If nums[i] > nums[j], it means we can append nums[i] to a wiggle subsequence that ended at nums[j] with a downward wiggle. The new length would be down[j] + 1. We take the maximum over all possible j.
up[i] = 1 + max(down[j]) for all j < i where nums[i] > nums[j].
Similarly, for down[i], we look for nums[j] where nums[i] < nums[j]. We can append nums[i] to a wiggle subsequence that ended at nums[j] with an upward wiggle. The new length would be up[j] + 1.
down[i] = 1 + max(up[j]) for all j < i where nums[i] < nums[j].
The base case is that any element by itself is a wiggle subsequence of length 1, so up[i] and down[i] are initialized to 1. The final answer is the maximum value in either up or down arrays after filling them.
import java.util.Arrays; public class Solution { public int wiggleMaxLength(int[] nums) { if (nums.length < 2) { return nums.length; } int n = nums.length; int[] up = new int[n]; int[] down = new int[n]; Arrays.fill(up, 1); Arrays.fill(down, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { up[i] = Math.max(up[i], down[j] + 1); } else if (nums[i] < nums[j]) { down[i] = Math.max(down[i], up[j] + 1); } } } int maxLength = 0; for (int i = 0; i < n; i++) { maxLength = Math.max(maxLength, Math.max(up[i], down[i])); } return maxLength; }}Complexity
Time
O(n^2), where n is the number of elements in the input array. The nested loops dominate the runtime.
Space
O(n), where n is the number of elements in the input array. We use two arrays, `up` and `down`, of size n.
Trade-offs
Pros
It is a standard and intuitive dynamic programming solution.
Guaranteed to find the correct optimal solution.
Cons
The time complexity is quadratic, which might be too slow for very large input arrays.
Requires extra space proportional to the input size.
A more efficient approach is to use a greedy strategy. The core idea is that we only need to track the length of the longest wiggle subsequence ending in an upward movement and one ending in a downward movement. When we iterate through the array, we can extend one of these sequences based on the current element's relation to the previous one. This avoids the need for the inner loop of the DP approach, reducing the complexity significantly.
Algorithm
- Handle the base case: if the array has fewer than 2 elements, return its length.
- Initialize two variables,
upanddown, to 1.upwill track the length of the longest wiggle subsequence ending with an upward wiggle, anddownwill track the length for a downward wiggle. - Iterate through the array from the second element (
i = 1ton-1). - At each element
nums[i], compare it with the previous elementnums[i-1]. - If
nums[i] > nums[i-1], we have an "up" slope. This can extend a subsequence that ended in a "down" slope. So, we updateup = down + 1. Thedownlength remains unchanged because we can't extend a down-slope sequence with an up-slope move from the immediately preceding element. - If
nums[i] < nums[i-1], we have a "down" slope. This can extend a subsequence that ended in an "up" slope. So, we updatedown = up + 1. Theuplength remains unchanged. - If
nums[i] == nums[i-1], the sequence is flat, which doesn't contribute to a wiggle. We do nothing and bothupanddownremain unchanged. - After the loop, the result is the maximum of the final
upanddownvalues.
Walkthrough
This approach can be seen as a space-optimized version of the O(n^2) DP solution. Instead of two arrays, we only need two variables, up and down, to store the lengths of the longest wiggle subsequences ending with a positive and negative difference, respectively.
We initialize up = 1 and down = 1, representing the subsequence formed by the first element. Then, we iterate from the second element. For each element nums[i], we consider the difference nums[i] - nums[i-1]:
- If
nums[i] > nums[i-1](an up-slope): We can form a new, longer subsequence ending with an up-slope by appendingnums[i]to any previous subsequence that ended with a down-slope. The longest such new sequence will have lengthdown + 1. We updateupto this new length. Thedownlength doesn't change, as we are on an up-slope. - If
nums[i] < nums[i-1](a down-slope): Similarly, we can extend a previous up-slope sequence. We updatedowntoup + 1. - If
nums[i] == nums[i-1]: The element is a duplicate of the previous one. It cannot extend a wiggle sequence, so we ignore it andupanddownremain the same.
This works because any consecutive run of increasing or decreasing numbers can be represented by just its start and end points in a wiggle subsequence. The greedy choice of always extending the sequence with the very next peak or valley proves to be optimal.
public class Solution { public int wiggleMaxLength(int[] nums) { if (nums.length < 2) { return nums.length; } // up: length of longest wiggle subsequence ending with a positive difference // down: length of longest wiggle subsequence ending with a negative difference int up = 1; int down = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[i-1]) { up = down + 1; } else if (nums[i] < nums[i-1]) { down = up + 1; } } return Math.max(up, down); }}Complexity
Time
O(n), where n is the number of elements in the input array. We perform a single pass through the array.
Space
O(1). We only use a few constant extra variables (`up`, `down`).
Trade-offs
Pros
Extremely efficient with linear time complexity.
Uses constant extra space, making it optimal in terms of memory.
Cons
The greedy logic can be less obvious to prove correct compared to the straightforward DP formulation.
Solutions
Solution
class Solution {public int wiggleMaxLength(int[] nums) { int up = 1, down = 1; for (int i = 1; i < nums.length; ++i) { if (nums[i] > nums[i - 1]) { up = Math.max(up, down + 1); } else if (nums[i] < nums[i - 1]) { down = Math.max(down, up + 1); } } return Math.max(up, down); }}class Solution {public: int wiggleMaxLength(vector<int> &nums) { int up = 1, down = 1; for (int i = 1; i < nums.size(); ++i) { if (nums[i] > nums[i - 1]) { up = max(up, down + 1); } else if (nums[i] < nums[i - 1]) { down = max(down, up + 1); } } return max(up, down); }};class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: up = down = 1 for i in range(1, len(nums)): if nums[i] > nums[i - 1]: up = max(up, down + 1) elif nums[i] < nums[i - 1]: down = max(down, up + 1) return max(up, down) # class Solution ( object ): def wiggleMaxLength ( self , nums ): """ :type nums: List[int] :rtype: int """ if not nums : return 0 up = down = 1 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 return max ( up , down )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.