Wiggle Subsequence solution and explanation
9 more videos on this problem
#Leetcode #376 Wiggle Subsequence #Dynamic ProgrammingCode with Alisha · 20:36 · 8K views
Wiggle Subsequence | Leetcode 376 | ArraysAyushi Sharma · 16:07 · 6K views
Wiggle Subsequence | Leetcode 376Coding Decoded · 13:12 · 6K views
#Leetcode #376 Wiggle Subsequence #Greedy AlgorithmCode with Alisha · 16:46 · 2K views
Leetcode - Wiggle Subsequence (Python)Timothy H Chang · 5:40 · 2K views
LeetCode 376. Wiggle SubsequenceHappy Coding · 15:57 · 1K views
Leetcode 376 Wiggle Subsequence | Coding Decoded SDE Revision SheetCoding Decoded · 2:04 · 773 views
Wiggle Subsequence | LeetCode 376 | Coders CampCoders Camp · 7:47 · 605 views
Daily Leetcode #824: Jul 03, 2022 - 376. Wiggle SubsequenceProgramming Live with Larry · 24:22 · 549 views
#Leetcode #376 Wiggle Subsequence #Golang ProgrammingThe Exception Handler · 24:17 · 348 views
The problem
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.
def wiggleMaxLength(nums):
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)
nums = [1, 7, 4, 9, 2, 5]
print(wiggleMaxLength(nums))public class Solution {
public 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);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 7, 4, 9, 2, 5};
System.out.println(sol.wiggleMaxLength(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
int up = 1, down = 1;
for (int 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);
}
int main() {
vector<int> nums = {1, 7, 4, 9, 2, 5};
cout << wiggleMaxLength(nums) << endl;
return 0;
}function wiggleMaxLength(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);
}
let nums = [1, 7, 4, 9, 2, 5];
console.log(wiggleMaxLength(nums));#include <stdio.h>
int wiggleMaxLength(int* nums, int numsSize){
if(numsSize < 2) return numsSize;
int up = 1, down = 1;
for(int i = 1; i < numsSize; ++i) {
if(nums[i] > nums[i-1])
up = down + 1;
else if(nums[i] < nums[i-1])
down = up + 1;
}
return (up > down) ? up : down;
}
int main() {
int nums[] = {1, 7, 4, 9, 2, 5};
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", wiggleMaxLength(nums, length));
return 0;
}using System;
public class Solution {
public 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);
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 7, 4, 9, 2, 5};
Console.WriteLine(sol.WiggleMaxLength(nums));
}
}The Python solution follows the greedy strategy approach to determine the maximum length of a wiggle subsequence. Using two counters up and down, we iterate through each element and update these counters based on the observed differences.
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.
def wiggleMaxLength(nums):
if len(nums) < 2:
return len(nums)
up = [1] * len(nums)
down = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
up[i] = max(up[i], down[j] + 1)
elif nums[i] < nums[j]:
down[i] = max(down[i], up[j] + 1)
return max(up[-1], down[-1])
nums = [1, 7, 4, 9, 2, 5]
print(wiggleMaxLength(nums))import java.util.Arrays;
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;
int[] up = new int[nums.length];
int[] down = new int[nums.length];
Arrays.fill(up, 1);
Arrays.fill(down, 1);
for (int i = 1; i < nums.length; ++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);
}
}
return Math.max(up[nums.length - 1], down[nums.length - 1]);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 7, 4, 9, 2, 5};
System.out.println(sol.wiggleMaxLength(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
vector<int> up(nums.size(), 1);
vector<int> down(nums.size(), 1);
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])
up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])
down[i] = max(down[i], up[j] + 1);
}
}
return max(up.back(), down.back());
}
int main() {
vector<int> nums = {1, 7, 4, 9, 2, 5};
cout << wiggleMaxLength(nums) << endl;
return 0;
}function wiggleMaxLength(nums) {
if (nums.length < 2) return nums.length;
let up = new Array(nums.length).fill(1);
let down = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let 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);
}
}
return Math.max(up[nums.length - 1], down[nums.length - 1]);
}
let nums = [1, 7, 4, 9, 2, 5];
console.log(wiggleMaxLength(nums));#include <stdio.h>
#include <stdlib.h>
int wiggleMaxLength(int* nums, int numsSize){
if(numsSize < 2) return numsSize;
int *up = (int*)malloc(numsSize * sizeof(int));
int *down = (int*)malloc(numsSize * sizeof(int));
for(int i = 0; i < numsSize; i++) {
up[i] = down[i] = 1;
}
for(int i = 1; i < numsSize; i++) {
for(int j = 0; j < i; j++) {
if(nums[i] > nums[j])
up[i] = (up[i] > down[j] + 1) ? up[i] : down[j] + 1;
else if(nums[i] < nums[j])
down[i] = (down[i] > up[j] + 1) ? down[i] : up[j] + 1;
}
}
int maxLen = 0;
for(int i = 0; i < numsSize; i++) {
if (up[i] > maxLen) maxLen = up[i];
if (down[i] > maxLen) maxLen = down[i];
}
free(up);
free(down);
return maxLen;
}
int main() {
int nums[] = {1, 7, 4, 9, 2, 5};
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", wiggleMaxLength(nums, length));
return 0;
}using System;
public class Solution {
public int WiggleMaxLength(int[] nums) {
if (nums.Length < 2) return nums.Length;
int[] up = new int[nums.Length];
int[] down = new int[nums.Length];
Array.Fill(up, 1);
Array.Fill(down, 1);
for (int i = 1; i < nums.Length; 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);
}
}
return Math.Max(up[nums.Length - 1], down[nums.Length - 1]);
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 7, 4, 9, 2, 5};
Console.WriteLine(sol.WiggleMaxLength(nums));
}
}The Python implementation is a straightforward simulation of dynamic programming for storing subsequence lengths. Analyzing all previous elements for each index allows updating up and down dynamically using conditional checks.
Time Complexity: O(n^2).
Space Complexity: O(n).
Approach 3: Dynamic Programming
We define f[i] as the length of the wiggle sequence ending at the ith element with an upward trend, and g[i] as the length of the wiggle sequence ending at the ith element with a downward trend. Initially, f[0] = g[0] = 1 because when there is only one element, the length of the wiggle sequence is 1. Initialize the answer as 1.
For f[i], where i geq 1, we enumerate j in the range [0, i), if nums[j] < nums[i], it means that i can be appended after j to form an upward wiggle sequence, then f[i] = max(f[i], g[j] + 1); if nums[j] > nums[i], it means that i can be appended after j to form a downward wiggle sequence, then g[i] = max(g[i], f[j] + 1). Then we update the answer to max(f[i], g[i]).
Finally, we return the answer.
The time complexity is O(n^2), and the space complexity is O(n). Where n is the length of the array nums.
function wiggleMaxLength(nums: number[]): number {
const n = nums.length;
const f: number[] = Array(n).fill(1);
const g: number[] = Array(n).fill(1);
let ans = 1;
for (let i = 1; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
f[i] = Math.max(f[i], g[j] + 1);
} else if (nums[i] < nums[j]) {
g[i] = Math.max(g[i], f[j] + 1);
}
}
ans = Math.max(ans, f[i], g[i]);
}
return ans;
}func wiggleMaxLength(nums []int) int {
n := len(nums)
f := make([]int, n)
g := make([]int, n)
f[0], g[0] = 1, 1
ans := 1
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
f[i] = max(f[i], g[j]+1)
} else if nums[j] > nums[i] {
g[i] = max(g[i], f[j]+1)
}
}
ans = max(ans, max(f[i], g[i]))
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n). |
| Dynamic Programming | Time Complexity: O(n^2). |
| Dynamic Programming | – |
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 |
Frequently asked questions
Is Wiggle Subsequence easy or hard?
Wiggle Subsequence is considered a medium-level problem. The DP formulation is straightforward, but recognizing that it can be reduced to a greedy O(n) solution with constant space requires deeper algorithmic insight.
How to solve Wiggle Subsequence in O(n)?
Iterate through the array and track two counters: up and down. If nums[i] > nums[i-1], set up = down + 1. If nums[i] < nums[i-1], set down = up + 1. This captures every direction change in a single pass, giving O(n) time and O(1) space.
What is the best approach for Wiggle Subsequence?
The optimal approach is a greedy algorithm that tracks two values: the best wiggle length ending with an upward difference and one ending with a downward difference. By updating these values during a single pass through the array, you get the correct answer in O(n) time and O(1) space.
What data structure is used in Wiggle Subsequence?
The problem mainly uses arrays and simple integer variables. The dynamic programming approach maintains two arrays (up and down), while the optimized greedy solution reduces them to two variables for constant space.
What is the time complexity of Wiggle Subsequence?
The optimal greedy solution runs in O(n) time because it scans the array once while updating two variables. A dynamic programming version also runs in O(n) time but uses O(n) space to maintain up and down arrays.
Wiggle Subsequence Python or Java solution approach?
Both Python and Java implementations typically follow the greedy approach. Maintain two integers (up and down), iterate through the array, and update them based on whether the current difference is positive or negative. The logic stays identical across languages.
Is Wiggle Subsequence asked at Google, Amazon, or Meta?
Wiggle Subsequence is a common medium-level array and greedy problem frequently used in technical interview preparation. Variations of alternating sequence or peak-valley problems have appeared in interviews at companies like Amazon, Google, and Meta.