Problem Description

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
• [1, 4, 7, 2, 5] is not a wiggle sequence because its first two differences are both positive
• [1, 7, 4, 5, 5] is not a wiggle sequence 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, you need to find and return the length of the longest wiggle subsequence that can be formed from nums.

The key insight is that you're looking for the longest subsequence (not necessarily consecutive elements) where the differences between adjacent elements in the subsequence alternate between positive and negative. You can skip elements from the original array to create this subsequence while maintaining the relative order of the selected elements.

Intuition

The problem asks for the longest wiggle subsequence, which means we need to track sequences that alternate between going up and down. This naturally leads us to think about maintaining two different states at each position - one for sequences ending with an upward trend and one for sequences ending with a downward trend.

Consider what happens at each element: if we're currently at position i, we can either extend a wiggle sequence by going up (if the previous element was smaller) or going down (if the previous element was larger). The key observation is that:

• To go up at position i, we need the previous part of the sequence to have been going down
• To go down at position i, we need the previous part of the sequence to have been going up

This alternating nature suggests we need to track two things separately:

• f[i]: the longest wiggle sequence ending at position i with an upward trend (the last move was up)
• g[i]: the longest wiggle sequence ending at position i with a downward trend (the last move was down)

For each position i, we look at all previous positions j where j < i:

• If nums[j] < nums[i], we can append nums[i] to create an upward move. The best previous sequence for this would be one that ended with a downward move at position j, which is g[j]. So f[i] = max(f[i], g[j] + 1)
• If nums[j] > nums[i], we can append nums[i] to create a downward move. The best previous sequence for this would be one that ended with an upward move at position j, which is f[j]. So g[i] = max(g[i], f[j] + 1)

By maintaining these two states and ensuring we alternate between them, we naturally capture the wiggle property of the sequence. The final answer is the maximum value among all f[i] and g[i] values.

Solution Approach

We implement a dynamic programming solution using two arrays to track the wiggle sequences:

1. Initialize the DP arrays: Create two arrays f and g, both of size n and initialized to 1:

   • f[i] represents the length of the longest wiggle sequence ending at index i with an upward trend
   • g[i] represents the length of the longest wiggle sequence ending at index i with a downward trend
   • All positions start with value 1 since a single element forms a valid wiggle sequence of length 1

2. Set up the answer variable: Initialize ans = 1 to track the maximum length found so far.

3. Fill the DP arrays: For each position i from 1 to n-1:

   • Examine all previous positions j from 0 to i-1
   • When nums[j] < nums[i]: This creates an upward trend from j to i
     • Update f[i] = max(f[i], g[j] + 1)
     • We use g[j] because to have an upward trend at i, we need the sequence at j to have ended with a downward trend
   • When nums[j] > nums[i]: This creates a downward trend from j to i
     • Update g[i] = max(g[i], f[j] + 1)
     • We use f[j] because to have a downward trend at i, we need the sequence at j to have ended with an upward trend
   • When nums[j] == nums[i]: Skip this case as equal consecutive elements don't form a wiggle

4. Update the answer: After processing each position i, update ans = max(ans, f[i], g[i]) to keep track of the longest wiggle sequence found so far.

5. Return the result: The final answer is the maximum length among all possible wiggle sequences ending at any position.

The time complexity is O(n²) due to the nested loops, and the space complexity is O(n) for storing the two DP arrays.

Example Walkthrough

Let's trace through the algorithm with the array nums = [1, 7, 4, 9, 2, 5].

Initial Setup:

• n = 6
• f = [1, 1, 1, 1, 1, 1] (longest wiggle ending with upward trend)
• g = [1, 1, 1, 1, 1, 1] (longest wiggle ending with downward trend)
• ans = 1

Processing i = 1 (nums[1] = 7):

• Check j = 0 (nums[0] = 1):
  • Since 1 < 7 (upward trend), update f[1] = max(1, g[0] + 1) = max(1, 2) = 2
• Result: f = [1, 2, 1, 1, 1, 1], g = [1, 1, 1, 1, 1, 1]
• Update ans = max(1, 2, 1) = 2

Processing i = 2 (nums[2] = 4):

• Check j = 0 (nums[0] = 1):
  • Since 1 < 4 (upward), f[2] = max(1, g[0] + 1) = 2
• Check j = 1 (nums[1] = 7):
  • Since 7 > 4 (downward), g[2] = max(1, f[1] + 1) = max(1, 3) = 3
• Result: f = [1, 2, 2, 1, 1, 1], g = [1, 1, 3, 1, 1, 1]
• Update ans = max(2, 2, 3) = 3

Processing i = 3 (nums[3] = 9):

• Check j = 0: 1 < 9, f[3] = max(1, g[0] + 1) = 2
• Check j = 1: 7 < 9, f[3] = max(2, g[1] + 1) = max(2, 2) = 2
• Check j = 2: 4 < 9, f[3] = max(2, g[2] + 1) = max(2, 4) = 4
• Result: f = [1, 2, 2, 4, 1, 1], g = [1, 1, 3, 1, 1, 1]
• Update ans = 4

Processing i = 4 (nums[4] = 2):

• Check j = 0: 1 < 2, f[4] = max(1, g[0] + 1) = 2
• Check j = 1: 7 > 2, g[4] = max(1, f[1] + 1) = 3
• Check j = 2: 4 > 2, g[4] = max(3, f[2] + 1) = max(3, 3) = 3
• Check j = 3: 9 > 2, g[4] = max(3, f[3] + 1) = max(3, 5) = 5
• Result: f = [1, 2, 2, 4, 2, 1], g = [1, 1, 3, 1, 5, 1]
• Update ans = 5

Processing i = 5 (nums[5] = 5):

• Check j = 0: 1 < 5, f[5] = max(1, g[0] + 1) = 2
• Check j = 1: 7 > 5, g[5] = max(1, f[1] + 1) = 3
• Check j = 2: 4 < 5, f[5] = max(2, g[2] + 1) = max(2, 4) = 4
• Check j = 3: 9 > 5, g[5] = max(3, f[3] + 1) = max(3, 5) = 5
• Check j = 4: 2 < 5, f[5] = max(4, g[4] + 1) = max(4, 6) = 6
• Result: f = [1, 2, 2, 4, 2, 6], g = [1, 1, 3, 1, 5, 5]
• Update ans = 6

Final Answer: 6

The longest wiggle subsequence is [1, 7, 4, 9, 2, 5] with differences (6, -3, 5, -7, 3) alternating between positive and negative.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the array nums. This is because we have two nested loops - the outer loop runs from index 1 to n-1 (which is O(n)), and for each iteration of the outer loop, the inner loop runs from 0 to i-1 (which in the worst case is also O(n)). Therefore, the overall time complexity is O(n) * O(n) = O(n^2).

The space complexity is O(n), where n is the length of the array nums. This is because we create two arrays f and g, each of size n, to store the dynamic programming states. These arrays require O(n) + O(n) = O(2n) = O(n) space. The other variables (ans, i, j) only require constant space O(1), so the overall space complexity is O(n).

Common Pitfalls

1. Inefficient Time Complexity - O(n²) Can Be Improved to O(n)

The current solution uses nested loops resulting in O(n²) time complexity, which is inefficient for large inputs. A critical observation is that we don't actually need to check all previous positions - we only need to track the best wiggle sequence lengths for the most recent up and down trends.

The Issue: The nested loop approach checks every pair (i, j) where j < i, but this is unnecessary. When processing position i, we only care about:

• The longest down-ending sequence before i (to potentially create an up-ending sequence at i)
• The longest up-ending sequence before i (to potentially create a down-ending sequence at i)

Optimized Solution:

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
      
        # Track the length of the longest wiggle sequence with:
        # - up: last difference is positive (going up)
        # - down: last difference is negative (going down)
        up = down = 1
      
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                # Current trend is upward
                # Can extend the best down-ending sequence
                up = down + 1
            elif nums[i] < nums[i-1]:
                # Current trend is downward
                # Can extend the best up-ending sequence
                down = up + 1
            # If nums[i] == nums[i-1], no update needed
      
        return max(up, down)

Why This Works:

• At each position, we only need to know the best up-ending and down-ending sequences seen so far
• When we see an upward trend, we can extend any down-ending sequence by 1
• When we see a downward trend, we can extend any up-ending sequence by 1
• The order of updates matters: we use the previous values of up/down to compute new values

This reduces time complexity from O(n²) to O(n) and space complexity from O(n) to O(1), making it much more efficient for large inputs while maintaining correctness.