algoadvance

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) might be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

• For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) are alternately positive and negative.
• In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.

Given an integer array nums, return the length of the longest wiggle subsequence.

Clarifying Questions

1. What if the input nums is empty?
   • Return 0.
2. What if the input nums contains only one element?
   • Return 1 since a single element is trivially a wiggle sequence.
3. How large can the input array nums be?
   • The input array can have up to (10^4) elements.
4. Are all values in nums unique?
   • No guarantee that all values are unique.

Strategy

To solve this problem, we can use a greedy approach:

1. Iterate through the array while keeping track of the previous difference (prevDiff) between consecutive elements.
2. Update the count of the wiggle sequence every time we find a valid “wiggle” (i.e., a change in the direction of the difference).
3. The count starts at 1 due to the first element of the array being part of the sequence by default.

Code

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)
    
    prevDiff = nums[1] - nums[0]
    count = 1 if prevDiff == 0 else 2

    for i in range(2, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and prevDiff <= 0) or (diff < 0 and prevDiff >= 0):
            count += 1
            prevDiff = diff
    
    return count

Time Complexity

• Time Complexity: (O(n)), where (n) is the length of nums. The algorithm iterates through the array once.
• Space Complexity: (O(1)), as we only use a few additional variables to store the differences and the count. No extra space proportional to the input size is used.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?