Simple Python O(n), space O(1) solution, one-pass and easy to understand


  • 0
    C

    The idea is pretty simple. We only update the count ans and the previous valid difference pred whenever a valid number shows up and skip others.

    pred is the difference between the latest valid number and the number before it (initialized with nums[1]-nums[0])
    A valid number must satisfy the condition of pred * diff < 0 (one positive and one negative).
    Corner cases are those with a lot of leading elements with the same value such as [1,1,1,1,1,3]. The condition diff!=0 and pred==0 would take care of these cases by updating pred whenever the first non-zero pred shows up.

    One-pass, time complexity O(n), space complexity O(1), run time ~32 ms

    def wiggleMaxLength(self, nums):
        if len(nums) < 2:
            return len(nums)
        pred = nums[1] - nums[0]
        ans = 1 + (pred!=0) 
        for i in xrange(2, len(nums)):
            diff = nums[i] - nums[i-1]
            if pred*diff < 0 or (diff!=0 and pred==0):
                ans += 1
                pred = diff
        return ans

  • 0
    L

    @cmc why does pred=diff have to be in the if statement? Can you show me a small case that shows this?


Log in to reply
 

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