376. Wiggle Subsequence

Description

The wiggleMaxLength problem requires us to find the length of the longest wiggle subsequence in an array. A wiggle sequence is defined as a series of numbers where the differences between successive numbers strictly alternate between positive and negative. The goal is to identify the maximum length of such a sequence from the input array nums.

Intuition

The idea is to track whether the difference between consecutive elements is increasing or decreasing. A "wiggle" happens when an increasing sequence is followed by a decreasing one, and vice versa. If we can count these "wiggles," we can derive the length of the longest wiggle subsequence.

Approach

1. Start with a counter initialized to 1 since any sequence of at least one element has a wiggle length of 1.
2. Track the previous "difference" (dif) between consecutive numbers, which helps determine whether the current number is part of a wiggle subsequence.
3. Traverse the array: - If the current number is greater than the next one and the previous difference was positive or undefined, increment the counter and mark the difference as negative. - If the current number is less than the next one and the previous difference was negative or undefined, increment the counter and mark the difference as positive.
4. Continue this process until all elements in the array have been processed.
5. Return the counter, which gives the length of the longest wiggle subsequence.

Complexity

Time Complexity:

O(n), where n is the length of the input array. We traverse the array only once.

Space Complexity:

O(1), as we use only a few extra variables to store state and counters.

Code

C++

class Solution {
public:
    int wiggleMaxLength(vector& nums) {
        if (nums.empty()) return 0;

        int count = 1;
        int dif = -1; // Initialize dif to -1 (undefined)

        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (dif == 1 || dif == -1) {
                    dif = 0;
                    count++;
                }
            } else if (nums[i] < nums[i + 1]) {
                if (dif == 0 || dif == -1) {
                    dif = 1;
                    count++;
                }
            }
        }
        return count;
    }
};

Python

class Solution:
    def wiggleMaxLength(self, nums):
        if not nums:
            return 0

        count = 1
        dif = None  # Use None to represent undefined

        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                if dif == 1 or dif is None:
                    dif = 0
                    count += 1
            elif nums[i] < nums[i + 1]:
                if dif == 0 or dif is None:
                    dif = 1
                    count += 1

        return count

Java

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 0) return 0;

        int count = 1;
        Integer dif = null; // Use null to represent undefined

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (dif == null || dif == 1) {
                    dif = 0;
                    count++;
                }
            } else if (nums[i] < nums[i + 1]) {
                if (dif == null || dif == 0) {
                    dif = 1;
                    count++;
                }
            }
        }
        return count;
    }
}

JavaScript

var wiggleMaxLength = function (nums) {
    let dif = undefined
    let count = 1
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            if (dif == 1 || dif == undefined) {
                dif = 0
                count = count + 1
            }
        }
        else if (nums[i] < nums[i + 1]) {
            if ((dif == 0 || dif == undefined)) {
                dif = 1
                count = count + 1
            }
        }
    } return count
};