My clean and readable python solution


  • 18
    Y
    Basic Idea: Binary search
    
    Elaboration: 
     if an element(not the right-most one) is smaller than its right neighbor, then there must be a peak element on its right, because the elements on its right is either 
       1. always increasing  -> the right-most element is the peak
       2. always decreasing  -> the left-most element is the peak
       3. first increasing then decreasing -> the pivot point is the peak
       4. first decreasing then increasing -> the left-most element is the peak  
    
       Therefore, we can find the peak only on its right elements( cut the array to half)
    
       The same idea applies to that an element(not the left-most one) is smaller than its left neighbor.
    
    
    
    Conditions:
         1. array length is 1  -> return the only index 
         2. array length is 2  -> return the bigger number's index 
         3. array length is bigger than 2 -> 
               (1) find mid, compare it with its left and right neighbors  
               (2) return mid if nums[mid] greater than both neighbors
               (3) take the right half array if nums[mid] smaller than right neighbor
               (4) otherwise, take the left half
    
    Run time: O(logn)
    Memory: constant
    Test cases: 
         [1]
         [1,2]
         [2,1]
         [1,2,3]
         [3,2,1]
         [2,1,3]
    
    
    def findPeakElement(self, nums):
        left = 0
        right = len(nums)-1
    
        # handle condition 3
        while left < right-1:
            mid = (left+right)/2
            if nums[mid] > nums[mid+1] and nums[mid] > nums[mid-1]:
                return mid
                
            if nums[mid] < nums[mid+1]:
                left = mid+1
            else:
                right = mid-1
                
        #handle condition 1 and 2
        return left if nums[left] >= nums[right] else right

  • 0

    Thanks for sharing! I am a little bit confused about the binary search algorithm. If the input is [10,9,8,6,5,13,2], it would skip the peak on the right part. What I have missed?


  • 0
    A

    "while left < right-1:" is a good one. Thanks buddy!


  • 2
    C

    a little change for the answer, 48ms, beats 82.40%.

    class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums)-1
    
        while left < right:
            mid = (left+right)/2
            if nums[mid] > nums[mid+1] and nums[mid] > nums[mid-1]:
                return mid
    
            if nums[mid] < nums[mid+1]:
                left = mid+1
            else:
                right = mid-1
    
        return left

  • 2

    @JayWong

    Hi there, I think the answer to your question is that we don't need to find ALL the peaks, nor even the HIGHEST peak.
    We just need to find a local peak.
    Even if we skip the peak on the right part, in your test case, we will still end up with a local peak on the left park
    hope this helps!


  • 0
    A

    @cheffyu Thanks for posting this optimization. It is more closer than to the normal binary search solution that students prepare at college. It is simple and is accepted. Thanks again.


  • 0
    X

    Thanks!Thanks!Thanks!Thanks!Thanks!Thanks!


Log in to reply
 

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