Wiggle Subsequence

Medium
315.

Wiggle Subsequence

Wiggle Subsequence is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Adobe interviews.

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 <= 40
  • 0 <= nums[i] <= 1000

Follow-up: The O(n²) DP is straightforward. Can you do it in O(n)?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • 0 <= nums[i] <= 1000

Follow-up: The O(n²) DP is straightforward. Can you do it in O(n)?

Hints for Wiggle Subsequence

  1. Hint 1

    Track two lengths: the best wiggle ending with an upward step and the best ending with a downward step.

  2. Hint 2

    A rise updates up from down + 1; a fall updates down from up + 1.

  3. 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

  1. Return the length for fewer than two elements.
  2. For each adjacent pair, update up or down as above.
  3. 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