Wiggle Subsequence — Solution in Python, Java & C++
Wiggle Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Wiggle Subsequence is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Greedy
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A wiggle sequence is one where the differences between successive numbers alternate strictly between positive and negative. A sequence of one element, and any two-element sequence with unequal values, count as wiggle sequences.
Given an integer array nums, return the length of the longest wiggle subsequence.
Example 1
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The whole array already wiggles.
Example 2
Input: nums = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Example 3
Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2
Constraints
1 <= nums.length <= 400 <= nums[i] <= 1000
Follow-up: The O(n²) DP is straightforward. Can you do it in O(n)?
Hints for Wiggle Subsequence
Hint 1
Track two lengths: the best wiggle ending with an upward step and the best ending with a downward step.
Hint 2
A rise updates
upfromdown + 1; a fall updatesdownfromup + 1.Hint 3
Equal neighbours change nothing — they never contribute a wiggle.
How to solve Wiggle Subsequence
Track the longest wiggle ending with a rise (up) and with a fall (down); a rise sets up = down + 1, a fall sets down = up + 1, equal neighbours change nothing.
Approach
- Return the length for fewer than two elements.
- For each adjacent pair, update
upordownas above. - Return
max(up, down).
Why it works
Only the direction of the last step matters for extending a wiggle. Greedily counting every direction change is optimal because a subsequence can always skip the middle of a monotone run.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Do not increment on plateaus; equal values contribute no wiggle.
Reference solution
Python
def wiggleMaxLength(nums) -> int:
if len(nums) < 2:
return len(nums)
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)Java
public static int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;
int up = 1, 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);
}C++
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2) return (int) nums.size();
int up = 1, down = 1;
for (size_t i = 1; i < nums.size(); i++) {
if (nums[i] > nums[i - 1]) up = down + 1;
else if (nums[i] < nums[i - 1]) down = up + 1;
}
return max(up, down);
}JavaScript
var wiggleMaxLength = function(nums) {
if (nums.length < 2) return nums.length;
let up = 1, down = 1;
for (let 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);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming