Python O(n) solution with explanation

  • 0

    A variable ct is used to track the length of wiggle array.
    Use two variables n1, n2 to track the latest two elements in the wiggle array, n is the coming candidate from the given array nums. Two scenarios can take place:

    1. unhappy case -- n1, n2, n are not wiggling, mathematically it can be expressed as:
      (n-n2) * (n2 - n1) >= 0,
      then we throw away either n1 or n2 (in my code, I always throw n2) and put n into the wiggle array. ct is not updated.
    2. happy case -- n1, n2, n are wiggling, then we simply add n to the wiggle list, equivalently ct +1.
    class Solution(object):
        def wiggleMaxLength(self, nums):
            :type nums: List[int]
            :rtype: int
            L = len(nums)
            if L <= 2:
                return L
            n1 = nums[0]
            n2 = nums[1]
            i = 2
            ct = 2
            while i < L:
                n = nums[i]
                if (n-n2) * (n2 - n1) >= 0:
                    n2 = n
                    n1 = n2
                    n2 = n
                    ct += 1
                i += 1
            return ct

Log in to reply

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