Wiggle Subsequence - Leetcode Solution

Problem Statement:

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

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 fewer than two elements is trivially a wiggle sequence.

A sequence nums is said to be strictly increasing if nums[i] < nums[i + 1] for all 0 <= i < nums.length - 1.

A sequence nums is said to be strictly decreasing if nums[i] > nums[i + 1] for all 0 <= i < nums.length - 1.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [1,7,4,9,2,5] Output: 6 Explanation: The entire sequence is a wiggle sequence.

Solution:

The approach that we will use to solve this problem is dynamic programming.

We will use two arrays, up[] and down[] to keep track of the longest wiggle sequence that ends with an increasing or decreasing element respectively.

If nums[i] > nums[i-1], then the i-th element is part of an up-sequence that ends with the i-th element. Thus, we can update the up[i] = down[i-1] + 1.

If nums[i] < nums[i-1], then the i-th element is part of a down-sequence that ends with the i-th element. Thus, we can update the down[i] = up[i-1] + 1.

We will then return the maximum of up[n-1] and down[n-1] as the answer.

Below is the Python implementation of the above approach:

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        up = [0] * n
        down = [0] * n
        up[0] = down[0] = 1
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                up[i] = down[i-1] + 1
                down[i] = down[i-1]
            elif nums[i] < nums[i-1]:
                down[i] = up[i-1] + 1
                up[i] = up[i-1]
            else:
                up[i] = up[i-1]
                down[i] = down[i-1]
        return max(up[n-1], down[n-1])

Time Complexity: O(n)

Space Complexity: O(n)

Explanation:

We initialize the up and down arrays with 0 and set the first element to 1 since the sequence with only 1 element is considered a wiggle sequence.

We then iterate over the array and compute the values for up and down arrays using the above formulae.

Finally, we return the maximum element of up and down arrays as the answer.

1