376. Wiggle Subsequence – Leetcode Solutions

Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: 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
Explanation: 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

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        # Edge case: if there is only one element, the length of the longest wiggle sequence is 1
        if len(nums) < 2:
            return len(nums)
        
        # Initialize the count to 1, as the first element is always counted in the wiggle sequence
        # `prev_diff` holds the previous difference between consecutive numbers
        # Start with None since there's no previous difference at the beginning
        count = 1
        prev_diff = 0  # initialize previous difference as zero
        
        # Iterate over nums from the second element onwards
        for i in range(1, len(nums)):
            # Calculate the current difference between consecutive elements
            diff = nums[i] - nums[i - 1]
            
            # Check if there's a change in the sign of `diff` relative to `prev_diff`
            if (diff > 0 and prev_diff <= 0) or (diff < 0 and prev_diff >= 0):
                # Increment the count because we have a wiggle (change in direction)
                count += 1
                # Update `prev_diff` to the current difference
                prev_diff = diff
        
        return count

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        // If the array has one element or less, return the size of the array.
        // Any single element sequence is trivially a wiggle sequence.
        int n = nums.size();
        if (n < 2) return n;
        
        // Initialize variables to count the up and down subsequences.
        // 'up' will track the length of the longest subsequence ending in an "up" wiggle (positive difference).
        // 'down' will track the length of the longest subsequence ending in a "down" wiggle (negative difference).
        int up = 1, down = 1;

        // Iterate through the array starting from the second element.
        for (int i = 1; i < n; ++i) {
            // Calculate the difference between the current and previous element.
            int diff = nums[i] - nums[i - 1];
            
            if (diff > 0) {
                // If difference is positive, we have an "up" wiggle.
                // Update 'up' as the previous 'down' + 1, because an "up" can follow a "down" wiggle.
                up = down + 1;
            } else if (diff < 0) {
                // If difference is negative, we have a "down" wiggle.
                // Update 'down' as the previous 'up' + 1, because a "down" can follow an "up" wiggle.
                down = up + 1;
            }
            // If diff == 0, do nothing, as consecutive equal elements do not form a wiggle.
        }

        // The maximum wiggle sequence length will be the larger of the two.
        return max(up, down);
    }
};

var wiggleMaxLength = function(nums) {
    // If the input array is empty or has only one element, return the length of nums (either 0 or 1).
    if (nums.length < 2) return nums.length;

    // Initialize two variables to track the length of the longest wiggle subsequence:
    // up: the longest wiggle subsequence that ends in a positive difference.
    // down: the longest wiggle subsequence that ends in a negative difference.
    let up = 1;
    let down = 1;

    // Iterate through the array starting from the second element.
    for (let i = 1; i < nums.length; i++) {
        // Calculate the difference between the current element and the previous one.
        let diff = nums[i] - nums[i - 1];

        // If the difference is positive, it means there's an "up" wiggle.
        if (diff > 0) {
            // Update the 'up' count by adding 1 to 'down' (the previous longest wiggle subsequence ending in a "down").
            up = down + 1;
        }
        // If the difference is negative, it means there's a "down" wiggle.
        else if (diff < 0) {
            // Update the 'down' count by adding 1 to 'up' (the previous longest wiggle subsequence ending in an "up").
            down = up + 1;
        }
        // If diff is zero, ignore it because consecutive equal elements don't affect the wiggle pattern.
    }

    // The result is the maximum length of wiggle subsequences ending in either up or down.
    return Math.max(up, down);
};

class Solution {
    public int wiggleMaxLength(int[] nums) {
        // If the array has less than two elements, it's trivially a wiggle sequence
        if (nums.length < 2) {
            return nums.length;
        }

        // Initialize two variables to track the length of wiggle subsequences
        // 'up' represents the longest subsequence ending with an increasing difference
        // 'down' represents the longest subsequence ending with a decreasing difference
        int up = 1;
        int down = 1;

        // Traverse the array starting from the second element
        for (int i = 1; i < nums.length; i++) {
            // Calculate the difference between the current element and the previous element
            int diff = nums[i] - nums[i - 1];

            if (diff > 0) {
                // If the difference is positive, this is an "up" wiggle
                // We increment the 'up' variable based on the previous 'down' length
                up = down + 1;
            } else if (diff < 0) {
                // If the difference is negative, this is a "down" wiggle
                // We increment the 'down' variable based on the previous 'up' length
                down = up + 1;
            }
            // If diff == 0, we do nothing as no wiggle occurs
        }

        // The result is the maximum length of a wiggle subsequence,
        // which can end in either an "up" or "down" wiggle
        return Math.max(up, down);
    }
}