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
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 - nums 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
@cmc why does pred=diff have to be in the if statement? Can you show me a small case that shows this?