# [Python] Documented solution in O(n) time that is easy to understand

• ``````class Solution(object):
def wiggleMaxLength(self, nums):
if not nums:
return 0
# we use this alternator to determine if we are
# falling into a valley or climbing up a peak
# False = falling, True = climbing
alternator = False
# this list will track the longest wiggle subsequence
wiggle_stack = []
wiggle_stack.append(nums[0])

for num in nums[1:]:
# if we have only one value we need to decide whether
# we start off by falling or climbing
if len(wiggle_stack) == 1:
# we're climbing
if num > wiggle_stack[-1]:
wiggle_stack.append(num)
# we're falling (notice that we purposefully ignore the == case)
elif num < wiggle_stack[-1]:
alternator = True
wiggle_stack.append(num)
# falling
elif not alternator:
# num is larger than current peak so we update
# the height of the peak to take the larger height
if num > wiggle_stack[-1]:
wiggle_stack[-1] = num
# num is less than current peak which means we
# have successfully fallen. Now we have to climb
elif num < wiggle_stack[-1]:
alternator = True
wiggle_stack.append(num)
# climbing
else:
# num is lower than current valley so we update
# the height of the valley to take the lower valley
if num < wiggle_stack[-1]:
wiggle_stack[-1] = num
# num is greater than current peak which means we
# have successfully climbed. Now we have to fall
elif num > wiggle_stack[-1]:
alternator = False
wiggle_stack.append(num)
return len(wiggle_stack)
``````

Here is the code without comments for the Python wizards out there!

``````class Solution(object):
def wiggleMaxLength(self, nums):
if not nums:
return 0
alternator = False
wiggle_stack = []
wiggle_stack.append(nums[0])
for num in nums[1:]:
if len(wiggle_stack) == 1:
if num > wiggle_stack[-1]:
wiggle_stack.append(num)
elif num < wiggle_stack[-1]:
alternator = True
wiggle_stack.append(num)
elif not alternator:
if num > wiggle_stack[-1]:
wiggle_stack[-1] = num
elif num < wiggle_stack[-1]:
alternator = True
wiggle_stack.append(num)
else:
if num < wiggle_stack[-1]:
wiggle_stack[-1] = num
elif num > wiggle_stack[-1]:
alternator = False
wiggle_stack.append(num)
return len(wiggle_stack)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.