Wiggle Subsequence
Medium · Greedy · Explanation and code example
Up and Down Subsequence Lengths
How it works
A wiggle subsequence alternates positive and negative differences. Track the best length ending with an upward move and with a downward move. An increase extends the downward state, while a decrease extends the upward state; equal adjacent values add nothing.
Steps
- Start both lengths at one.
- Compare adjacent values and update the matching direction state.
- Return the larger length.
Complexity
- Time: O(n).
- Space: O(1).
Things to watch for
- Equal values are skipped.
- The answer is a subsequence, so turning points matter more than every value.
- A nonempty constant array has answer one.
Python code example
import itertools
class Solution:
def wiggleMaxLength(self, nums: list[int]) -> int:
increasing = 1
decreasing = 1
for a, b in itertools.pairwise(nums):
if b > a:
increasing = decreasing + 1
elif b < a:
decreasing = increasing + 1
return max(increasing, decreasing)
C++ code example
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int increasing = 1;
int decreasing = 1;
for (int i = 1; i < nums.size(); ++i)
if (nums[i] > nums[i - 1])
increasing = decreasing + 1;
else if (nums[i] < nums[i - 1])
decreasing = increasing + 1;
return max(increasing, decreasing);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.