#376

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Wiggle Subsequence

Find the longest wiggle subsequence in an integer array using state transition dynamic programming with greedy optimization for efficiency.

array dynamic programming greedy

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.

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.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i]$ as the length of the wiggle sequence ending at the $i$th element with an upward trend, and $g[i]$ as the length of the wiggle sequence ending at the $i$th element with a downward trend. Initially, $f[0] = g[0] = 1$ because when there is only one element, the length of the wiggle sequence is $1$. Initialize the answer as $1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 1
        f = [1] * n
        g = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    f[i] = max(f[i], g[j] + 1)
                elif nums[j] > nums[i]:
                    g[i] = max(g[i], f[j] + 1)
            ans = max(ans, f[i], g[i])
        return ans

Continue Practicing

#410 split array largest sum #435 non overlapping intervals #122 best time to buy and sell stock ii