Peak Index in a Mountain Array

---

Peak Index in a Mountain Array: An array arr a mountain if the following properties hold:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  1. arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  2. arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1:

Input: arr = [0,1,0]
Output: 1

---

Example 2:

Input: arr = [0,2,1,0]
Output: 1

---

Example 3:

Input: arr = [0,10,5,2]
Output: 1

---

Constraints:

• 3 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^6
• arr is guaranteed to be a mountain array.

---

Try this Problem on your own or check similar problems:

1. Find Peak Element
2. Find in Mountain Array

Solution:

Java

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

JavaScript

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

Python

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

C++

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

---

Time/Space Complexity:

• Time Complexity: O(log n)
• Space Complexity: O(1)

---

Explanation:

We have a modified binary search. Each time we find a mid we check if it's larger than the next element, if it is then we know it's potentially our peak element so we place end at mid (note it is not mid-1 because we cannot exclude element mid, since it could be our peak). If, however the element is smaller than its successor we know it can't be the peak so we place the start to mid + 1 (we can discard the current mid since we know it is not the peak).