The Wiggle Subsequence problem asks for the maximal-length subsequence where differences alternate in sign. We approach this with state transition dynamic programming, maintaining two states: up and down wiggle lengths. This allows a linear pass using greedy updates while capturing all necessary transitions to guarantee correctness.
Problem Statement
Given an integer array, a wiggle sequence is defined as one where consecutive differences strictly alternate between positive and negative. A single element or two elements with unequal values trivially form a wiggle sequence. Your task is to find the maximum length of such a subsequence within the array.
A subsequence is formed by deleting any number of elements (including zero) while preserving the relative order of remaining elements. Return the length of the longest wiggle subsequence possible for the input array.
Examples
Example 1
Input: nums = [1,7,4,9,2,5]
Output: 6
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
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
Example details omitted.
Constraints
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
Solution Approach
Dynamic Programming with State Transition
Maintain two arrays or variables representing the longest wiggle subsequence ending with an upward or downward difference. For each number, update these states based on the previous number's comparison to capture alternating differences.
Greedy Linear Pass Optimization
Instead of full DP arrays, keep two variables up and down. For each number, if it increases from the previous, increment up from down; if it decreases, increment down from up. This captures the maximal wiggle sequence in O(n) time and O(1) space.
Edge Cases and Subsequence Tracking
Handle arrays of length 1 or 2 specially, as they are trivially wiggle sequences. Avoid counting consecutive equal elements since they break the wiggle property, ensuring the state transition logic only updates on strict alternation.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) due to a single pass through the array. Space complexity is O(1) using two variables for up and down states instead of full DP arrays, optimized from the naive O(n) DP solution.
What Interviewers Usually Probe
- Checking if you correctly identify and track up and down states for DP transitions.
- Asking about handling consecutive equal numbers that do not contribute to wiggle subsequence.
- Expecting linear O(n) optimization using greedy updates rather than full DP arrays.
Common Pitfalls or Variants
Common pitfalls
- Treating consecutive equal numbers as valid wiggle differences.
- Overcomplicating DP with full arrays instead of maintaining just up/down states.
- Failing to handle edge cases where array length is 1 or 2.
Follow-up variants
- Return the actual longest wiggle subsequence instead of just its length.
- Count the number of distinct wiggle subsequences of maximal length.
- Adapt the problem to allow zero differences as valid for subsequence formation.
How GhostInterview Helps
- Provides step-by-step state transition guidance for up and down sequences.
- Highlights edge cases like consecutive duplicates and minimal-length arrays.
- Optimizes solution to linear time using greedy updates while maintaining correctness.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is a wiggle subsequence?
A wiggle subsequence alternates strictly between increasing and decreasing differences between consecutive elements.
Why do we use up and down states in DP for Wiggle Subsequence?
Up and down states capture the length of the longest subsequence ending with a positive or negative difference, essential for correct state transitions.
Can consecutive equal elements be part of the wiggle subsequence?
No, equal elements do not contribute to alternating differences and should be skipped in state updates.
What is the time complexity of the optimal solution?
The greedy linear pass solution achieves O(n) time by updating only two variables, up and down, per element.
How do I handle arrays of length 1 or 2?
An array of length 1 is trivially a wiggle sequence of length 1; a two-element array with unequal values forms a wiggle sequence of length 2.
Need direct help with Wiggle Subsequence instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Wiggle Subsequence from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve the 'Split Array Largest Sum' problem by minimizing the largest sum across k subarrays using dynamic programming and binary search.
Open problem page#435 Non-overlapping IntervalsDetermine the minimum number of intervals to remove from a list to ensure no intervals overlap using dynamic programming and greedy insights.
Open problem page#122 Best Time to Buy and Sell Stock IIMaximize stock profit by using a greedy approach to buy and sell multiple times, with state transition dynamic programming.
Open problem page