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.

Examples

Example 1:

1
2
3

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:

1
2
3
4

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:

1
2

Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2

Solution

Method 1 - Dynamic Programming DP

At each index in the array, the value can be in one of three states:

  • “up” if nums[i] > nums[i-1],
  • “down” if nums[i] < nums[i-1],
  • or “equal” if nums[i] == nums[i-1].

We use two arrays, up[] and down[], to track the maximum wiggle subsequence length at each position. If the current value is greater than the previous, update up[i] = down[i-1] + 1 and keep down[i] unchanged. If it’s less, set down[i] = up[i-1] + 1 and leave up[i] as before. If the values are equal, both arrays remain the same as the previous index.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
	public int wiggleMaxLength(int[] nums) {
		
		if( nums.length == 0 ) return 0;
		
		int[] up = new int[nums.length];
		int[] down = new int[nums.length];
		
		up[0] = 1;
		down[0] = 1;
		
		for(int i = 1 ; i < nums.length; i++){
			if( nums[i] > nums[i-1] ){
				up[i] = down[i-1]+1;
				down[i] = down[i-1];
			}else if( nums[i] < nums[i-1]){
				down[i] = up[i-1]+1;
				up[i] = up[i-1];
			}else{
				down[i] = down[i-1];
				up[i] = up[i-1];
			}
		}
		
		return Math.max(down[nums.length-1],up[nums.length-1]);
	}
}

Complexity

  • ⏰ Time complexity: O(n). You iterate through the array once, updating the up and down arrays at each step.
  • 🧺 Space complexity: O(n). Two arrays of size n (up[] and down[]) are used to store the results for each position.

Method 2 - Space Optimized DP

Intuition

Instead of keeping track of the entire history, we only need to know the length of the longest wiggle subsequence ending with an “up” or a “down” at the previous step. This allows us to use two variables instead of arrays.

Approach

  • Initialize two variables, up and down, both set to 1.
  • Iterate through the array from the second element:
    • If the current number is greater than the previous, set up = down + 1.
    • If the current number is less than the previous, set down = up + 1.
    • If equal, do nothing.
  • At the end, return the maximum of up and down.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
	public int wiggleMaxLength(int[] nums) {
		if (nums.length <= 1) {
			return nums.length;
		}
	
		int up = 1;
		int down = 1;
	
		for (int i = 1; i < nums.length; i++) {
			if (nums[i - 1] < nums[i]) {
				up = down + 1;
			} else if (nums[i - 1] > nums[i]) {
				down = up + 1;
			}
		}
		return Math.max(up, down);
	}
}

Complexity

  • ⏰ Time complexity: O(n). Single pass through the array.
  • 🧺 Space complexity: O(1).  Only two variables are used.

Method 3 - Greedy

Intuition

A wiggle subsequence alternates between increasing and decreasing. We only need to count the number of times the direction of the difference between consecutive elements changes.

Approach

  • Initialize a counter (starting at 1) and a variable to track the previous difference.
  • Iterate through the array:
    • For each element, calculate the difference with the previous element.
    • If the difference changes sign (from positive to negative or vice versa), increment the counter and update the previous difference.
  • Return the counter as the length of the longest wiggle subsequence.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	public int wiggleMaxLength(int[] nums) {
		if (nums.length<2) return 1;
	
		int count = 1;
	
		int prevDiff = 0;
		for (int i = 1; i<nums.length; i++) {
			int diff = nums[i] - nums[i - 1];
			if ((diff > 0 && prevDiff<= 0) || (diff<0 && prevDiff >= 0)) {
				// the equals in prevDiff<= 0 && prevDiff >=0 can only be used at the first iteration, otherwise prevDiff will never be zero afterwards
				count++;
				prevDiff = diff;
			}
		}
		return count;
	}
}

Complexity

  • ⏰ Time complexity: O(n). Single pass through the array.
  • 🧺 Space complexity: O(1). Only a few variables are used.