LeetCode 376: Wiggle Subsequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 376: Wiggle Subsequence?

LeetCode 376: Wiggle Subsequence provides an integer array, and your task is to find the length of the longest subsequence where the differences between consecutive elements alternate in sign (positive, negative, positive, etc.). A subsequence can skip elements but must preserve order. It’s a problem that tests your ability to track alternating patterns efficiently!

Problem Statement

• Input:
• nums: List of integers.
• Output: Integer - Length of the longest wiggle subsequence.
• Rules:
• Subsequence must alternate between up (increasing) and down (decreasing).
• Single element is a wiggle of length 1.
• Consecutive equal elements don’t count as wiggle.

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10⁴

Examples

• Input: nums = [1,7,4,9,2,5]
• Output: 6
• Full sequence [1,7,4,9,2,5] wiggles: 1<7>4<9>2<5 (length 6).
• Input: nums = [1,17,5,10,13,15,10,5,16,8]
• Output: 7
• [1,17,10,13,10,16,8]: 1<17>10<13>10<16>8 (length 7).
• Input: nums = [1,2,3,4,5,6,7,8,9]
• Output: 2
• [1,2] or [1,9] (monotonic, max wiggle is 2).

These show the wiggle pattern—let’s solve it!

Understanding the Problem: Finding the Longest Wiggle

To tackle LeetCode 376 in Python, we need to: 1. Identify a subsequence where differences alternate (up, down, up, ...). 2. Maximize its length. 3. Handle edge cases like monotonic or single-element arrays.

A naive approach might try all subsequences, but that’s exponential. Instead, we’ll use:

• Best Solution: Dynamic programming with two arrays—O(n) time, O(n) space—fast and clear.
• Alternative Solution: Greedy approach—O(n) time, O(1) space—intuitive and lean.

Let’s wiggle with the best solution!

Best Solution: Dynamic Programming with Two Arrays

Why This Is the Best Solution

The dynamic programming approach with two arrays runs in O(n) time by tracking the longest wiggle ending at each position with either an up or down move. It’s the best for clarity—using two states (up and down) to build the solution systematically while ensuring optimal length!

How It Works

Think of it like tracking wiggles:

• Two Arrays:
• up[i]: Length of longest wiggle ending at nums[i] with an up move.
• down[i]: Length ending with a down move.
• Update:
• If nums[i] > nums[i-1]: up[i] = down[i-1] + 1, down[i] = down[i-1].
• If nums[i] < nums[i-1]: down[i] = up[i-1] + 1, up[i] = up[i-1].
• If nums[i] == nums[i-1]: up[i] = up[i-1], down[i] = down[i-1].
• Base: up[0] = down[0] = 1 (single element).
• Result: Max of up[n-1] and down[n-1].

It’s like building the longest zigzag path!

Step-by-Step Example

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

• Init: up = [1,0,0,0,0,0], down = [1,0,0,0,0,0].
• i=1 (7): 7 > 1:
• up[1] = down[0] + 1 = 2.
• down[1] = down[0] = 1.
• up = [1,2,0,0,0,0], down = [1,1,0,0,0,0].
• i=2 (4): 4 < 7:
• down[2] = up[1] + 1 = 3.
• up[2] = up[1] = 2.
• up = [1,2,2,0,0,0], down = [1,1,3,0,0,0].
• i=3 (9): 9 > 4:
• up[3] = down[2] + 1 = 4.
• down[3] = down[2] = 3.
• up = [1,2,2,4,0,0], down = [1,1,3,3,0,0].
• i=4 (2): 2 < 9:
• down[4] = up[3] + 1 = 5.
• up[4] = up[3] = 4.
• up = [1,2,2,4,4,0], down = [1,1,3,3,5,0].
• i=5 (5): 5 > 2:
• up[5] = down[4] + 1 = 6.
• down[5] = down[4] = 5.
• up = [1,2,2,4,4,6], down = [1,1,3,3,5,5].
• Result: max(up[5], down[5]) = max(6, 5) = 6.

For nums = [1,2,3]:

• i=1: up[1] = 2, down[1] = 1.
• i=2: up[2] = 2, down[2] = 1.
• Result: 2.

Code with Explanation

Here’s the Python code using DP with two arrays:

Copy codeclass Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return 1

        # DP arrays: up[i] ends with up, down[i] ends with down
        up = [1] * len(nums)
        down = [1] * len(nums)

        # Compute wiggle lengths
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                up[i] = down[i-1] + 1
                down[i] = down[i-1]
            elif nums[i] < nums[i-1]:
                down[i] = up[i-1] + 1
                up[i] = up[i-1]
            else:  # Equal
                up[i] = up[i-1]
                down[i] = down[i-1]

        return max(up[-1], down[-1])

Explanation

• Lines 3-6: Handle edge cases: empty (0), single (1).
• Lines 8-9: Initialize up and down with 1 (each element alone is a wiggle).
• Lines 11-20: DP loop:
• If nums[i] > nums[i-1]: Up move extends down, down stays.
• If nums[i] < nums[i-1]: Down move extends up, up stays.
• If equal: No wiggle, copy previous.
• Line 22: Return max of final up and down lengths.
• Time: O(n)—single pass.
• Space: O(n)—two arrays.

This is like tracking a wiggly dance—step-by-step to the max!

Alternative Solution: Greedy Approach

Why an Alternative Approach?

The greedy approach also runs in O(n) time but uses O(1) space by counting wiggles directly, updating lengths based on the last two elements’ direction. It’s leaner—great for space efficiency and intuition, though less explicit than DP!

How It Works

• Track: Maintain up and down counts, update based on direction.
• Update:
• Up move: up = down + 1.
• Down move: down = up + 1.
• Equal: No change.
• Result: Max of up and down.

Step-by-Step Example

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

• Init: up=1, down=1.
• 7 > 1: up = down + 1 = 2, down = 1.
• 4 < 7: down = up + 1 = 3, up = 2.
• 9 > 4: up = down + 1 = 4, down = 3.
• 2 < 9: down = up + 1 = 5, up = 4.
• 5 > 2: up = down + 1 = 6, down = 5.
• Result: max(6, 5) = 6.

Code with Explanation

Copy codeclass Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return 1

        # Track up and down wiggles with O(1) space
        up = down = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                up = down + 1
            elif nums[i] < nums[i-1]:
                down = up + 1

        return max(up, down)

Explanation

• Lines 8-9: Initialize up and down to 1.
• Lines 11-14: Greedy update:
• Up move: up extends down.
• Down move: down extends up.
• Equal: No update (implicit).
• Line 16: Return max length.
• Time: O(n)—single pass.
• Space: O(1)—two variables.

It’s like counting wiggles on the fly—lean and quick!

Comparing the Two Solutions

• DP with Two Arrays (Best):
• Time: O(n)—linear pass.
• Space: O(n)—arrays.
• Pros: Clear state tracking.
• Cons: More memory.
• Greedy (Alternative):
• Time: O(n)—linear.
• Space: O(1)—minimal.
• Pros: Space-efficient, simple.
• Cons: Less explicit states.

DP wins for clarity, greedy for space!

Additional Examples and Edge Cases

• []: 0.
• [1]: 1.
• [1,1,1]: 1 (no wiggle).

Both handle these, greedy uses less space.

Complexity Breakdown

• DP:
• Time: O(n).
• Space: O(n).
• Greedy:
• Time: O(n).
• Space: O(1).

Both are fast, greedy is leaner.

Key Takeaways

• DP: Track all wiggles—clear and fast!
• Greedy: Count on the go—lean and quick!
• Wiggles: Patterns drive solutions.
• Python Tip: Arrays or vars rock—see [Python Basics](/python/basics).

Final Thoughts: Find That Wiggle

LeetCode 376: Wiggle Subsequence in Python is a wiggly challenge. DP with two arrays is the clarity champ, while greedy offers space efficiency. Want more? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 1143: Longest Common Subsequence. Ready to wiggle? Visit Solve LeetCode 376 on LeetCode and trace that path today!