Wiggle Subsequence — Editorial

Opening the reading…

Intuitionwhy only direction changes matter

A wiggle sequence is defined by the signs of its consecutive differences: positive, negative, positive, or the reverse. Equal values contribute no direction at all, so a zero difference cannot extend the sequence. The answer therefore depends on how many times the chosen subsequence can alternate between rising and falling, not on the actual sizes of those rises and falls.

When the sequence is currently rising, another rising value does not create a new wiggle. Keep the later value anyway, because it is the most recent endpoint and is at least as useful for a future fall. When the direction changes, that new value creates one more element in the subsequence. This replacement is the greedy choice: preserve the current length while making the endpoint ready for the next opposite direction.

Scan adjacent values and classify each difference as positive, negative, or zero. Count the first nonzero direction as the second element, then count a difference whenever its sign is opposite to the last accepted sign. Zero differences are skipped, and the last accepted sign is not changed by them. The scan is equivalent to keeping the best possible endpoint after every turn without storing the subsequence itself.

Approachone pass with the last accepted direction

Return nums.size() when the array has fewer than two values, because a one-element array is already a wiggle sequence and no difference can be formed.

Compute the first difference and set the answer to 2 only when it is nonzero; otherwise start at 1 because equal adjacent values do not establish a direction.

Store the first difference as prevDiff, including zero, so the first later positive or negative difference can establish the initial direction without a special second scan.

For every later adjacent pair, compute diff = nums[i] - nums[i - 1], because only the sign of this difference determines whether the current direction changed.

Accept diff when it is positive and prevDiff is nonpositive, or when it is negative and prevDiff is nonnegative; these conditions count a real turn while treating zero as no direction.

Increase the answer and replace prevDiff only after accepting a turn, because replacing it on a same-direction or zero difference would lose the last useful direction and could count a false turn.

Return the count after the scan, because every accepted turn contributes exactly one additional selected element and skipped differences cannot extend a wiggle.

Complexitythe scan uses constant working memory

MEASURE	BOUND	WHY
Time	O(n)	The loop examines each adjacent pair once, and each pair performs only constant-time arithmetic and comparisons. No pair is revisited, so the work grows linearly and remains O(n) for increasing, decreasing, alternating, or equal-heavy input.
Space	O(1) extra space	The algorithm stores only the count, the last accepted difference, and the current difference. The returned value is output rather than working memory, so it is excluded; the extra space stays O(1) for every input shape.

Here n is the length of nums.

Annotated solutionC++ · greedy one-pass implementation

CPPGreedy scan that counts each accepted change of direction.

#include <vector>
using namespace std;

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

        int prevDiff = nums[1] - nums[0];
        int count = (prevDiff != 0) ? 2 : 1;

        for (int i = 2; i < nums.size(); ++i) {
            int diff = nums[i] - nums[i - 1];

            if ((diff > 0 && prevDiff <= 0) ||
                (diff < 0 && prevDiff >= 0)) {
                ++count;
                prevDiff = diff;
            }
        }

        return count;
    }
};

The important placement is prevDiff = diff inside the acceptance condition. A same-direction difference may move the conceptual endpoint, but it does not change the wiggle direction, so it cannot affect the count. Updating prevDiff only for an accepted turn makes the stored value represent the last meaningful sign, while the <= and >= comparisons allow a zero difference to be ignored naturally.

The dynamic programming alternativea clearer state model at O(n squared) time and O(n) space

A standard dynamic programming formulation keeps two values for every position. up[i] is the longest wiggle subsequence ending at i whose last difference is positive, and down[i] is the corresponding length when the last difference is negative. For every earlier position j, a rise from nums[j] to nums[i] can extend down[j], while a fall can extend up[j].

CPPDynamic programming over every earlier endpoint and both possible final directions.

#include <algorithm>
#include <vector>
using namespace std;

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

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

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

        return max(up[n - 1], down[n - 1]);
    }
};

This alternative is not an optimisation. It is a more explicit arrangement that records the best answer ending at every index, which can be useful when you need to reconstruct or inspect endpoint states. It costs O(n squared) time because every pair of indices is compared and O(n) extra space for the two state arrays, while the greedy version compresses all needed information into constant space.