Find Peak in log(n) Time

Photo by Magda Ehlers from Pexels

The question that we’re going to walk through today is actually pretty easy, but could be a little bit tricky.

Given an unsorted array of numbers in which all elements are distinct, find a peak. A number is a peak if:
- It is greater than its left and right neighbours
- It is the first or last element on the list and it is greater than its only neighbour

(You only need to return any of the peak number)

To make it clearer, let’s see some of the examples:

List: [1, 2, 5, 4, 3]
Peak: 5
List: [1, 2, 9, 4, 5, 6, 7]
Peak: 9 or 7
List: [11, 10, 9, 4, 5, 1, 7]
Peak: 11 or 5 or 7
List: [1, 2, 3, 4, 5]
Peak: 5
List: [5, 4, 3, 2, 1]
Peak: 5

The most naive solution to this is to just go through each element one-by-one and see if it’s qualified as a peak. This solution will take O(n) time complexity at the worst case and O(1) for space complexity which is super for most algorithm problem. So, here comes the tricky part, solve it with O(log(n)) time complexity!

Here’s the trick, when you see this kind of problem where you are given a list of elements (usually numbers) and you have to find 1 element that is the maximum or minimum, or peak, etc. with time complexity of O(log(n)), always remember to first consider using Binary Search.

Usually Binary Search is being used in sorted array(it could also mean Bitonic array, or array that’s sorted in some other ways), but this one is a little bit different as we can’t sort the array.

In Binary Search, we always check the middle value and see if it’s qualified to be a peak, if not then we change the start or end pointer so that we get a new middle value. Let’s try to solve this problem by hand using this example:

List: [11, 10, 9, 4, 5, 1, 7]
start + (end - start) //2
Start = 0
End = 6
Mid = 3
[11, 10, 9, 4, 5, 1, 7]
            |
The middle value is less than both of the neighbours, so in this case we can either choose to find the peak on the left side or the right side of the array. As you can see if we chose the left side, we will get 9 or 11 as our peak, otherwise the right side will give us either 5 or 7. All the elements in the array is distinct, so we can be sure that if we choose any of the neighbours that is greater than the middle value, we will find a peak.
For now let's choose the side that has greater number, in this case 9 (as 9 > 5).
Start = 0
End = 3
Mid = 1
[11, 10, 9, 4, 5, 1, 7]
      |
Start = 0
End = 1
Mid = 0
[11, 10, 9, 4, 5, 1, 7]
 |
Peak = 11

Here’s the code written in Python to solve this problem:

def findPeak(lst):
   start, end = 0, len(lst) - 1
   while start < end:
      mid = start + (end - start) // 2
      
      # Check if it's a peak
      if lst[mid] > lst[mid - 1] and lst[mid] > lst[mid + 1]:
         return lst[mid]
      if lst[mid - 1] > lst[mid + 1]:
         end = mid
      else:
         start = mid + 1
   return lst[start]

Time Complexity: O(log(n))
Space Complexity: O(1) (it’s actually half of the original solution)