Find Peak Element

---

Find Peak Element: A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

---

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number
1 where the peak element is 2, or index number 5 where the peak element is 6.

---

Constraints:

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i + 1] for all valid i.

---

Try this Problem on your own or check similar problems:

1. Peak Index in a Mountain Array
2. Find a Peak Element II

Solution:

Java

public int findPeakElement(int[] nums) {
    int start = 0, end = nums.length - 1;
    while(start < end){
        int mid = start + (end - start) / 2;
        if(nums[mid] < nums[mid+1]){
            start = mid + 1;
        }else{
            end = mid;
        }
    }
    return start;
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function (nums) {
  let start = 0;
  let end = nums.length - 1;
  while (start < end) {
    let mid = Math.floor(start + (end - start) / 2);
    if (nums[mid] < nums[mid + 1]) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }
  return start;
};

Python

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        start = 0
        end = len(nums) - 1
        while start < end:
            mid = start + (end - start) // 2
            if nums[mid] < nums[mid + 1]:
                start = mid + 1
            else:
                end = mid
        return start

C++

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
         int start = 0;
        int end = nums.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < nums[mid + 1]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(logn)
• Space Complexity: O(1)

---

Explanation:

The solution and intuition is identical to the Peak Index in a Mountain Array. First we note that the last element is always larger than the element out of array boundary, same goes for the first element nums[-1] = nums[n] = -∞. Also we can return any peak (any local maximum) as stated by the problem statement. We can use those two information to move in the direction of the rising slope (everytime choosing the larger element of nums[mid] and nums[mid+1]), so there are two scenarios:

• We either push to the end and every element is larger than the previous (or next if we're going to the left) leading to rising slope and we would just return the last element since nums[-1] = nums[n] = -∞
• Our slope fails but we have already recorded the element before the slope went down (with end = mid), so start will eventually converge to it and will be returned as our result