Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

376. Wiggle Subsequence - Leetcode Solution

Code Implementation

class Solution:
    def wiggleMaxLength(self, nums):
        if not nums:
            return 0
        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)
      
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int up = 1, down = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i-1])
                up = down + 1;
            else if (nums[i] < nums[i-1])
                down = up + 1;
        }
        return max(up, down);
    }
};
      
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 0) return 0;
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i-1]) {
                up = down + 1;
            } else if (nums[i] < nums[i-1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}
      
var wiggleMaxLength = function(nums) {
    if (!nums.length) return 0;
    let up = 1, down = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i-1]) {
            up = down + 1;
        } else if (nums[i] < nums[i-1]) {
            down = up + 1;
        }
    }
    return Math.max(up, down);
};

Problem Description

Given an array of integers nums, find the length of the longest subsequence that is a wiggle sequence. 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 single element is trivially a wiggle sequence of length 1.
  • You may not reorder the elements; the subsequence must be derived by deleting some elements (possibly none) without changing the order of the remaining elements.
  • Elements can only be used once and must appear in their original order.
  • Return the length of the longest such subsequence.

Thought Process

At first glance, the problem seems similar to finding the longest increasing or decreasing subsequence, but with the added twist that the direction must alternate. A brute-force approach would try all possible subsequences and check if they wiggle, but this is highly inefficient. To optimize, we need to track, for each position, whether the previous difference was up or down, and try to extend the sequence accordingly. We can use dynamic programming or greedy ideas to avoid unnecessary recomputation. The key realization is that at each step, we only need to know the length of the longest wiggle subsequence ending with an "up" or a "down" at that point.

Solution Approach

The most efficient approach uses two variables to track the length of the longest wiggle subsequence ending with an up or a down:
  • Step 1: Initialize two variables, up and down, both to 1. These represent the longest wiggle subsequence ending with an upward or downward difference, respectively.
  • Step 2: Iterate through the array from the second element onward.
  • Step 3: For each element:
    • If nums[i] > nums[i-1], it means we can extend a sequence that previously ended with a "down", so set up = down + 1.
    • If nums[i] < nums[i-1], we can extend a sequence that previously ended with an "up", so set down = up + 1.
    • If nums[i] == nums[i-1], do nothing (no wiggle).
  • Step 4: At the end, the answer is the maximum of up and down.
This approach is efficient because we only need constant space and a single pass through the array.

Example Walkthrough

Consider nums = [1, 7, 4, 9, 2, 5]:
  • Start: up = 1, down = 1
  • i=1: 7 > 1, so up = down + 1 = 2
  • i=2: 4 < 7, so down = up + 1 = 3
  • i=3: 9 > 4, so up = down + 1 = 4
  • i=4: 2 < 9, so down = up + 1 = 5
  • i=5: 5 > 2, so up = down + 1 = 6
The longest wiggle subsequence has length 6, corresponding to the entire array. At each step, we only needed to remember the last "up" and "down" lengths and update accordingly.

Time and Space Complexity

  • Brute-force: Trying all subsequences is O(2^n) time and O(n) space, which is impractical for large inputs.
  • Optimized approach (as described above):
    • Time Complexity: O(n), since we make a single pass through the array.
    • Space Complexity: O(1), since we only use two variables (up and down).

Summary

The Wiggle Subsequence problem is elegantly solved by tracking the length of the longest subsequence ending with an upward or downward difference. By carefully updating these two variables as we iterate through the array, we avoid redundant calculations and achieve optimal efficiency. The solution is both simple and powerful, demonstrating the effectiveness of greedy and dynamic programming ideas.