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.
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); }}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.