Friedrich Ewald My Personal Website

Leetcode: Find peak element

Given an array n of integers, find one peak in O(log*n) time. A peak is defined as a number where the two numbers immediately left and right are strictly less than the number. Numbers outside of the bounds of this array are considered to be smaller. We can leverage the binary search algorithm to find a peak. This is because we can split the array in two parts and look in the middle. If left and right are smaller, it is a peak, otherwise we move in the direction of the higher element. This allows us to find the peak in log*n steps.

from typing import List

class Solution:
  def findPeakElement(self, nums: List[int]) -> int:
    l = 0
    r = len(nums) - 1
    m = (l+r)//2

    while l < r:
      peak = nums[m]
      lsm = True if m == 0 or nums[m] > nums[m-1] else False
      rsm = True if m == len(nums)-1 or nums[m] > nums[m+1] else False
      if lsm and rsm:
        return m
      if lsm:
        l = m+1
        r = m
      m = (l+r)//2
    return m

if __name__ == '__main__':
  s = Solution().findPeakElement
  print(s([1,2,3,1]), 2)
  print(s([5,4,3,2,1,0,-1,-2,-3,-4]), 0)
  print(s([0,1,2,3,4,5,6,5,4,3]), 6)

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.