Wiggle Subsequence

Updated on 03 July, 2025
Wiggle Subsequence header image

Problem Statement

In the context of arrays, a wiggle sequence is defined as a sequence where the differences between successive numbers in the sequence strictly alternate between positive and negative. The initial difference in the sequence could either be positive or negative. Notably, a single element sequence, as well as any two-element sequence with distinct numbers, automatically qualify as wiggle sequences.

To elaborate, consider the sequence [1, 7, 4, 9, 2, 5] which qualifies as a wiggle sequence. This is deduced from the difference between successive elements: (6, -3, 5, -7, 3), which alternates between positive and negative. Conversely, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] do not meet the criteria for a wiggle sequence. The former sequence has its first two differences as positive and hence does not alternate, while the latter has a difference of zero which is neither positive nor negative.

A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Given an integer array nums, the task is to determine the length of the longest wiggle subsequence within nums.

Examples

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

Approach and Intuition

A nuanced understanding of the problem can be attributed to the observation of changes in the trend of the sequence. When considering how to determine the longest wiggle subsequence, a straightforward method involves:

  1. Define a default sequence starting with the first two distinct elements which establish the initial trend (either increasing or decreasing).
  2. Traverse through the array and compare each element to the previous one to detect a change in the gradient (from increasing to decreasing or vice versa).
  3. Whenever a change in the trend is observed, include that element in the wiggle subsequence. This captures the point where the sequence wiggles.
  4. Continue this until all elements are assessed.

This simpler greedy approach leverages capturing each point of transition to construct the longest possible wiggle sequence.

Understanding Through Examples:

  • Example 1: For input nums = [1,7,4,9,2,5], we observe that the entire sequence forms a wiggle pattern. Hence, the longest wiggle subsequence includes all elements, so the output is 6.

  • Example 2: For input nums = [1,17,5,10,13,15,10,5,16,8], a possible longest wiggle subsequence could be [1, 17, 5, 10, 13, 10, 16, 8]. This subsequence has consistent alternation between rise and fall, giving a length of 7.

  • Example 3: Given nums = [1,2,3,4,5,6,7,8,9], this array is consistently increasing, thus only two elements can be used to form a valid wiggle subsequence (e.g., [1, 2] or any two consecutive numbers), resulting in the maximum length being 2.

By following these intuitions and steps, we can efficiently determine the length of the longest wiggle subsequence without needing any advanced data structures, utilizing basic array manipulations and conditional assessments.

Solutions

  • Java
java
public class Solution {
    public int getMaxWiggleLength(int[] sequence) {
        if (sequence.length < 2)
            return sequence.length;
        int lastDifference = sequence[1] - sequence[0];
        int length = lastDifference != 0 ? 2 : 1;
        for (int index = 2; index < sequence.length; index++) {
            int currentDiff = sequence[index] - sequence[index - 1];
            if ((currentDiff > 0 && lastDifference <= 0) || (currentDiff < 0 && lastDifference >= 0)) {
                length++;
                lastDifference = currentDiff;
            }
        }
        return length;
    }
}

The given Java solution is designed to calculate the maximum length of a wiggle subsequence from an input array. A wiggle subsequence is one where the differences between successive elements strictly alternate between positive and negative. Here's how this solution works:

  • Check if the input sequence has fewer than two elements. If so, return the length of the sequence, as a sequence with less than two elements doesn't have enough items to wiggle.
  • Initialize lastDifference to capture the difference between the first two elements of the sequence. This will help track the last direction of wiggle (up or down).
  • Set length of the wiggle subsequence. If the first difference is non-zero (indicative of a wiggle start), set length to 2. Otherwise, set it to 1 as there's no wiggle with only identical or single element.
  • Iterate through the sequence starting from the third element:
    • Calculate the current difference between the current and the previous element.
    • Check if the current difference and the last difference change signs (one is positive and the other is negative or zero and vice versa). This change in sign indicates a wiggle.
    • If a wiggle is detected, increment the length of the wiggle subsequence and update lastDifference to the current difference.
  • Return the computed length, which will be the maximum length of the wiggle subsequence.

This solution efficiently determines the maximum wiggle sequence length in a single pass through the input array with a time complexity of O(n), where n is the number of elements in the sequence.

Comments

No comments yet.