Python 40ms O(n) with Math Intuition - Local Max, Local Min and Saddle points


  • 1
    A

    This is just a simple math question disguised in cs language. To paraphrase, it is equiv. to:

    "Find all local min / max points on xy plane (where x is simply 0 - n-1".

    To do that, in discrete math, you just need to find all x[i] where:

    1. x[i] > x[i-1] and x[i] < x[i+1]
    2. x[i] > x[i-1] and x[i] > x[i+1]

    The only caveat is SADDLE points.

    The code is written in a rush that can def be simplified, yet it passed all testcases within 40ms, so it is acceptable

    class Solution(object):
        def wiggleMaxLength(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            peaks, troughs, n = [], [], len(nums)
            if n == 1:
                return 1
            for i in range(n):
                if i == 0:
                    if nums[i] > nums[i+1]:
                        peaks.append(i)
                    if nums[i] < nums[i+1]:
                        troughs.append(i)
                elif i == n-1:
                    if nums[i] > nums[i-1]:
                        peaks.append(i)
                    if nums[i] < nums[i-1]:
                        troughs.append(i)
                else:
                    if nums[i] >= nums[i-1] and nums[i] > nums[i+1]:
                        if nums[i] == nums[i-1]:
                            k = i
                            while k > 0 and nums[k] == nums[k-1]:
                                k -= 1
                            if k == 0 or nums[k] > nums[k-1]:
                                peaks.append(i)
                        else:
                            peaks.append(i)
                    if nums[i] <= nums[i-1] and nums[i] < nums[i+1]:
                        if nums[i] == nums[i-1]:
                            k = i 
                            while k > 0 and nums[k] == nums[k-1]:
                                k -= 1
                            if k == 0 or nums[k] < nums[k-1]:
                                troughs.append(i)
                        else:
                            peaks.append(i)            
                
            return len(peaks)+len(troughs)
    

  • 0

  • 0
    A

    @StefanPochmann suppose we found all local min and max, first they satisfy the requirement of the problem - i.e. wiggling sequence, and we cannot get another "wiggle", because any wiggle requires a "kink" - i.e. our data cannot be monotonically increasing or decreasing - which means we must have a local min or max - this is however contradictory of our assumption that we have found ALL local min and max.


  • 0
    A

    @StefanPochmann should change my wording - not "equivalent", but "Finding all local mins and maxs" is "sufficient but not required" to get "wiggle subsequence"...


Log in to reply
 

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