Find Peak Element

Share

A peak element is one greater than its neighbors. Given an array nums, find a peak element and return its index. The array may have multiple peaks; return any peak.

Example 1
Input: nums=[1,2,3,1] → Output: 2
Example 2
Input: nums=[1,2,1,3,5,6,4] → Output: 5

Solution Approach

Binary search: if nums[mid] < nums[mid+1], there must be a peak on the right side. Otherwise there is a peak at mid or to the left.

  • lo=0, hi=n-1.
  • If nums[mid] < nums[mid+1]: peak is to the right, lo=mid+1.
  • Else: peak is at mid or left, hi=mid.
  • When lo==hi, that is the peak index.
Java
class Solution {
    public int findPeakElement(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < nums[mid + 1]) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}
  • Time Complexity: O(log N)
  • Space Complexity: O(1)