Wiggle Subsequence - Solution & Explanation
Problem Statement
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?
Approach Overview
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 1: Greedy Approach
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.
Complexity
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Dynamic Programming
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.
Code
C
C++
Java
Python
C#
JavaScript
Go
TypeScript
Complexity
Time Complexity: O(n^2).
Space Complexity: O(n).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n). |
| Dynamic Programming | Time Complexity: O(n^2). |
Detailed Complexity Analysis
| 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 |
Video Solution
#Leetcode #376 Wiggle Subsequence #Dynamic Programming • Code with Alisha • 8,746 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Wiggle Subsequence easy or hard?
How to solve Wiggle Subsequence in O(n)?
What is the best approach for Wiggle Subsequence?
What data structure is used in Wiggle Subsequence?
What is the time complexity of Wiggle Subsequence?
Wiggle Subsequence Python or Java solution approach?
Is Wiggle Subsequence asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Wiggle Subsequence with our built-in code editor and test cases.
Practice on FleetCode