We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Wiggle Subsequence

Number: 376

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, a wiggle sequence is one where the successive differences between numbers strictly alternate between positive and negative. A subsequence is obtained by deleting some elements without changing the order. The task is to find the length of the longest wiggle subsequence.

Key Insights

  • A single element or two distinct elements are trivial wiggle subsequences.
  • The sign of the difference between successive elements is what matters; only count changes when the sign flips (ignoring zeros).
  • A greedy approach can be applied by iterating once through the array and tracking the current direction (positive or negative).
  • Dynamic programming is also possible but not necessary since O(n) time can be achieved with the greedy approach.

Space and Time Complexity

Time Complexity: O(n) – we traverse the array once.
Space Complexity: O(1) – only a few extra variables are used.

Solution

We start by checking if the list has fewer than two elements; if so, that length is the answer. Then, we initialize a counter (result) and a variable to store the last non-zero difference between consecutive elements. For each element in the array, calculate the current difference. If the current difference and the previous difference have opposite signs (one positive and one negative), then it indicates a valid wiggle and we increase our counter and update the previous difference. This ensures every valid "turn" is counted in the subsequence.

Code Solutions

# Python solution using a greedy approach with detailed comments

def wiggleMaxLength(nums):
    # If the list is empty or has one element, return its length
    if not nums:
        return 0
    n = len(nums)
    if n < 2:
        return n
    
    # Initialize the previous difference to 0 and count the first element
    prev_diff = 0
    count = 1  # At least one element is always part of the subsequence
    
    # Iterate through the list starting from the second element
    for i in range(1, n):
        # Calculate the current difference
        curr_diff = nums[i] - nums[i - 1]
        # Check for a valid direction change:
        # curr_diff > 0 and previous difference was negative OR
        # curr_diff < 0 and previous difference was positive
        if (curr_diff > 0 and prev_diff <= 0) or (curr_diff < 0 and prev_diff >= 0):
            count += 1       # Increment our count as this element is part of the wiggle subsequence
            prev_diff = curr_diff  # Update the previous difference for future comparisons
    
    return count

# Example usage:
print(wiggleMaxLength([1,7,4,9,2,5]))  # Expected output: 6
← Back to All Questions