Coder's Cat

## LeetCode: Find Peak Element

2020-02-07

Challenge Description

## Native solution with Linear Scan

The naive solution is scan the array, check whether a element is peak.

Time complexity: $O(N)$.

Because we can return any peak, so there are 3 cases:

• arr[0] is peak

• arr[arr.size()-1] is peak

• peak is in the range of 1...arr.size()-2

In this case, we just need to find the first index, which meets the condition of arr[index] > arr[index + 1]. So we can make the code more simpler:

Using recursive binary search, the time complexity is $O(logN)$.

Join my Email List for more insights, It's Free!😋