
Description
The wiggleMaxLength
problem requires us to find the length of the longest wiggle subsequence in an array. A wiggle sequence is defined as a series of numbers where the differences between successive numbers strictly alternate between positive and negative. The goal is to identify the maximum length of such a sequence from the input array nums
.
Intuition
The idea is to track whether the difference between consecutive elements is increasing or decreasing. A "wiggle" happens when an increasing sequence is followed by a decreasing one, and vice versa. If we can count these "wiggles," we can derive the length of the longest wiggle subsequence.
Approach
- Start with a counter initialized to 1 since any sequence of at least one element has a wiggle length of 1.
- Track the previous "difference" (
dif
) between consecutive numbers, which helps determine whether the current number is part of a wiggle subsequence. - Traverse the array: - If the current number is greater than the next one and the previous difference was positive or undefined, increment the counter and mark the difference as negative. - If the current number is less than the next one and the previous difference was negative or undefined, increment the counter and mark the difference as positive.
- Continue this process until all elements in the array have been processed.
- Return the counter, which gives the length of the longest wiggle subsequence.
Complexity
Time Complexity:
O(n), where n
is the length of the input array. We traverse the array only once.
Space Complexity:
O(1), as we use only a few extra variables to store state and counters.
Code
C++
class Solution {
public:
int wiggleMaxLength(vector& nums) {
if (nums.empty()) return 0;
int count = 1;
int dif = -1; // Initialize dif to -1 (undefined)
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (dif == 1 || dif == -1) {
dif = 0;
count++;
}
} else if (nums[i] < nums[i + 1]) {
if (dif == 0 || dif == -1) {
dif = 1;
count++;
}
}
}
return count;
}
};
Python
class Solution:
def wiggleMaxLength(self, nums):
if not nums:
return 0
count = 1
dif = None # Use None to represent undefined
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
if dif == 1 or dif is None:
dif = 0
count += 1
elif nums[i] < nums[i + 1]:
if dif == 0 or dif is None:
dif = 1
count += 1
return count
Java
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 0) return 0;
int count = 1;
Integer dif = null; // Use null to represent undefined
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (dif == null || dif == 1) {
dif = 0;
count++;
}
} else if (nums[i] < nums[i + 1]) {
if (dif == null || dif == 0) {
dif = 1;
count++;
}
}
}
return count;
}
}
JavaScript
var wiggleMaxLength = function (nums) {
let dif = undefined
let count = 1
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (dif == 1 || dif == undefined) {
dif = 0
count = count + 1
}
}
else if (nums[i] < nums[i + 1]) {
if ((dif == 0 || dif == undefined)) {
dif = 1
count = count + 1
}
}
} return count
};