Wiggle Subsequence Problem

Problem Description

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

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 sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative. In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences.

Naive Approach (Brute Force)

A brute force approach would involve generating all possible subsequences of the given array and checking each subsequence to see if it's a wiggle sequence. Then, keep track of the length of the longest wiggle subsequence found. This approach is highly inefficient.

Complexity Analysis

• Time Complexity: O(2^n * n), where n is the length of the input array. Generating all subsequences takes O(2^n) time, and checking if a subsequence is a wiggle sequence takes O(n) time in the worst case.
• Space Complexity: O(n) in the worst case due to the recursive call stack.

Optimal Approach (Dynamic Programming or Greedy)

We can solve this problem using dynamic programming or a greedy approach in O(n) time.

Dynamic Programming

Let up[i] be the length of the longest wiggle subsequence ending at index i with a positive difference. Let down[i] be the length of the longest wiggle subsequence ending at index i with a negative difference.

Then, the recurrence relations are:

• up[i] = up[j] + 1 if nums[i] > nums[j] and j < i
• down[i] = down[j] + 1 if nums[i] < nums[j] and j < i

Greedy Approach

A more efficient approach can be achieved with a greedy algorithm. The main idea is to keep track of the last peak and valley seen so far. We iterate through the array and update the peak and valley accordingly.

Algorithm:

1. Initialize up = 1 and down = 1.
2. Iterate through the array from index 1.
3. If nums[i] > nums[i-1], it means we have a potential up-wiggle. Update up = down + 1.
4. If nums[i] < nums[i-1], it means we have a potential down-wiggle. Update down = up + 1.
5. Return max(up, down).

Code (Greedy)

def wiggleMaxLength(nums):
    if not nums:
        return 0

    up = 1
    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)

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array, since we iterate through the array once.
• Space Complexity: O(1), as we use only a constant amount of extra space for the up and down variables.

Edge Cases

• Empty array: return 0.
• Array with one element: return 1.
• Array with two different elements: return 2.
• Array with all same elements: return 1.

Example

nums = [1, 7, 4, 9, 2, 5]

1. up = 1, down = 1
2. i = 1, nums[1] = 7 > nums[0] = 1, up = down + 1 = 2
3. i = 2, nums[2] = 4 < nums[1] = 7, down = up + 1 = 3
4. i = 3, nums[3] = 9 > nums[2] = 4, up = down + 1 = 4
5. i = 4, nums[4] = 2 < nums[3] = 9, down = up + 1 = 5
6. i = 5, nums[5] = 5 > nums[4] = 2, up = down + 1 = 6

Return max(up, down) = 6