Python solution with detailed explanation


  • 0
    G

    Solution

    Find Peak Element https://leetcode.com/problems/find-peak-element/?tab=Description

    Algorithm

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

    Another method to code the above algorithm

    • The other solution is cleaner.
    • You account for boundary values in the code using nums[-1] = float('-inf') and nums[n] = float('-inf')
    • We find prev and next as nums[mid-1] and nums[mid+1]. If mid-1 is less than 0 or mid+1 is greater than len(nums)-1, return float('-inf').
    class Solution(object):
        def findPeakElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            lo, hi = 0, len(nums)-1
            while lo <= hi:
                mid = lo + int((hi-lo)/2)
                prev = nums[mid-1] if mid-1 >= 0 else float('-inf')
                nxt = nums[mid+1] if mid+1 <= len(nums)-1 else float('-inf')
                if prev < nums[mid] and nxt < nums[mid]:
                    return mid
                elif mid-1 >= 0 and nums[mid-1] > nums[mid]:
                    hi = mid -1
                else:
                    lo = mid + 1
            return
    

Log in to reply
 

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