Wiggle Subsequence - Practice Coding Problems

Wiggle Subsequence - 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.

Input & Output

Example 1 — Standard Wiggle Sequence

$ Input: nums = [1,7,4,9,2,5]

› Output: 6

💡 Note: The entire array forms a wiggle sequence with differences [+6,-3,+5,-7,+3] alternating between positive and negative. All 6 elements can be included.

Example 2 — Non-Wiggle Array

$ Input: nums = [1,4,7,2,5]

› Output: 4

💡 Note: The differences are [+3,+3,-5,+3]. The first two differences are both positive, so we can pick subsequence [1,7,2,5] with differences [+6,-5,+3] for length 4.

Example 3 — Equal Elements

$ Input: nums = [1,7,4,5,5]

› Output: 4

💡 Note: The last difference is zero (5-5=0), so we exclude one of the final 5s. Optimal subsequence is [1,7,4,5] with length 4.

Constraints

1 ≤ nums.length ≤ 1000
0 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,7,4,9,2,5] with elements

Find Differences

Calculate differences: +6, -3, +5, -7, +3

Check Alternation

Differences alternate signs: positive, negative, positive, negative, positive

Key Takeaway

🎯 Key Insight: A wiggle subsequence is longest when we include all local peaks and valleys where the trend changes

Asked in

G Google 15 M Microsoft 12 A Amazon 8 F Facebook 6

The key insight is that only local peaks and valleys matter for the longest wiggle subsequence. We can use a greedy approach that counts trend changes in O(n) time, or dynamic programming tracking up/down sequences ending at each position. Best approach: Greedy. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check which ones are wiggle sequences
Greedy - Track Trend Changes	O(n)	O(1)	Only count elements where the trend changes from ascending to descending or vice versa
Dynamic Programming	O(n²)	O(n)	Use two DP arrays to track ascending and descending wiggle sequences ending at each position

Brute Force - Check All Subsequences — Algorithm Steps

Generate all 2^n possible subsequences
For each subsequence, check if differences alternate signs
Keep track of the maximum length wiggle subsequence found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n possible subsequences

Validate

Check each subsequence for wiggle pattern

Maximum

Return length of longest valid wiggle subsequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isWiggle(int* seq, int len) {
    if (len <= 2) return true;
    
    for (int i = 1; i < len - 1; i++) {
        int diff1 = seq[i] - seq[i-1];
        int diff2 = seq[i+1] - seq[i];
        
        if (diff1 == 0 || diff2 == 0) return false;
        if ((diff1 > 0) == (diff2 > 0)) return false;
    }
    return true;
}

int generateSubsequences(int* nums, int numsSize, int idx, int* current, int currentSize) {
    if (idx == numsSize) {
        return isWiggle(current, currentSize) ? currentSize : 0;
    }
    
    // Don't include current element
    int maxLen = generateSubsequences(nums, numsSize, idx + 1, current, currentSize);
    
    // Include current element
    current[currentSize] = nums[idx];
    int withCurrent = generateSubsequences(nums, numsSize, idx + 1, current, currentSize + 1);
    maxLen = maxLen > withCurrent ? maxLen : withCurrent;
    
    return maxLen;
}

int solution(int* nums, int numsSize) {
    if (numsSize <= 1) return numsSize;
    int* current = (int*)malloc(numsSize * sizeof(int));
    int result = generateSubsequences(nums, numsSize, 0, current, 0);
    free(current);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

Generate 2^n subsequences, each taking O(n) time to validate

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack and temporary subsequence storage

⚡ Linearithmic Space

185.0K Views

Medium Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler