Wiggle Subsequence

Share

Find length of longest wiggle subsequence (alternating up/down differences).

Example 1
Input: nums=[1,7,4,9,2,5] → Output: 6
Example 2
Input: nums=[1,17,5,10,13,15,10,5,16,8] → Output: 7

Solution Approach

Greedy: count peaks and valleys. Track direction of last counted difference.

  • Track up and down counts, both start at 1
  • For each pair: if nums[i]>nums[i-1] and last was down: up++
  • If nums[i]
  • Return max(up, down)
Java
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);
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)