algoadvance

Leetcode 376. Wiggle Subsequence

Problem Statement

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.

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 second being not alternating and the third containing equal elements.

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

Clarifying Questions

1. Q: Can the elements of the array be negative or zero? A: Yes. The elements of the array can be any integers, including negative and zero.

2. Q: What is the constraint on the size of the array? A: The size of the array can be up to 1000 elements.

3. Q: Is an array with a single element considered a wiggle sequence? A: Yes, an array with a single element or an empty array is trivially a wiggle sequence.

Strategy

The idea is to track the lengths of subsequences that end in a peak or a valley for every element in the array. We can do this with two state variables:

• up[i] which stores the length of the longest wiggle subsequence ending in an increase at index i.
• down[i] which stores the length of the longest wiggle subsequence ending in a decrease at index i.

Initialize up[0] and down[0] to 1 since a single element is already a wiggle sequence. Then, as we iterate through the array from the second element, we update these states:

1. If nums[i] > nums[i-1], it forms a peak, so up[i] = down[i-1] + 1.
2. If nums[i] < nums[i-1], it forms a valley, so down[i] = up[i-1] + 1.
3. If nums[i] == nums[i-1], it doesn’t contribute to a wiggle therefore, up[i] = up[i-1] and down[i] = down[i-1].

The result will be the maximum of the final up and down.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int wiggleMaxLength(std::vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;

        std::vector<int> up(n, 1), down(n, 1);

        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                up[i] = down[i - 1] + 1;
                down[i] = down[i - 1];
            } else if (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 std::max(up[n - 1], down[n - 1]);
    }
};

Time Complexity

• Time Complexity: (O(n)), where (n) is the length of the array.
  • We iterate through the array once.
• Space Complexity: (O(n)), for storing the up and down vectors.

An optimization is possible to reduce space complexity to (O(1)) by using two variables instead of arrays to keep the lengths. Here’s the optimized version:

#include <vector>
#include <algorithm>

class Solution {
public:
    int wiggleMaxLength(std::vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;

        int up = 1, down = 1;

        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }

        return std::max(up, down);
    }
};

Time Complexity for Optimized Version

• Time Complexity: (O(n)), where (n) is the length of the array.
• Space Complexity: (O(1)), constant space for the up and down variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?