Solution: Wiggle Subsequence

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #376 (Medium): Wiggle Subsequence

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

• 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 because its first two differences are positive and the second because its last difference is zero.

A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

---

Examples:

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

Example 2:
Input:	nums = [1,17,5,10,13,15,10,5,16,8]
Output:	7
Explanation:	There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Example 3:
Input:	nums = [1,2,3,4,5,6,7,8,9]
Output:	2

---

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The key realization here is that any number that lies in the middle of a stretch of the same direction is extraneous, because the more extreme numbers are the better choices to keep, as they allow for a larger likelihood that a subsequent number will be a directional change.

So the simple answer here is to count the inflection points in our input array (N) where the direction changes. There are several ways to do this, but in this solution, we can keep a directional flag (up) to keep track of the current direction and then increment our answer (ans) and invert up when a change is found.

One tricky thing lies in setting the initial direction. Per the instructions, the first number can represent any direction, so we'll have to wait until the first time we see a different number to set our direction. We can check this with a simple while loop before the main loop.

Once we finish, we can return ans.

---

Implementation:

All but Javascript will require an additional check before the main loop to account for an input array with all the same number.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var wiggleMaxLength = function(N) {
    let len = N.length, i = 1
    while (N[i] === N[i-1]) i++
    let up = N[i-1] > N[i], ans = 1
    for (; i < len; i++)
        if ((up && N[i] < N[i-1]) || (!up && N[i] > N[i-1]))
            up = !up, ans++
    return ans
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def wiggleMaxLength(self, N: List[int]) -> int:
        lenN, i = len(N), 1
        while i < lenN and N[i] == N[i-1]: i += 1
        if i == lenN: return 1
        up, ans = N[i-1] > N[i], 1
        while i < lenN:
            if (up and N[i] < N[i-1]) or (not up and N[i] > N[i-1]):
                up = not up
                ans += 1
            i += 1
        return ans

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int wiggleMaxLength(int[] N) {
        int len = N.length, i = 1, ans = 1;
        while (i < len && N[i] == N[i-1]) i++;
        if (i == len) return 1;
        boolean up = N[i-1] > N[i];
        for (; i < len; i++)
            if ((up && N[i] < N[i-1]) || (!up && N[i] > N[i-1])) {
                up = !up;
                ans++;
            }
        return ans;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int wiggleMaxLength(vector<int>& N) {
        int len = N.size(), i = 1, ans = 1;
        while (i < len && N[i] == N[i-1]) i++;
        if (i == len) return 1;
        bool up = N[i-1] > N[i];
        for (; i < len; i++)
            if ((up && N[i] < N[i-1]) || (!up && N[i] > N[i-1]))
                up = !up, ans++;
        return ans;
    }
};