852. Peak Index in a Mountain Array

1. Description

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:
  • arr[0] < arr[1] < … < arr[i - 1] < arr[i]
  • 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.

2. Example

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

3. Constraints

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

4. Solutions

Binary Search

n = arr.size()
Time complexity: O(logn)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int peakIndexInMountainArray(const vector<int> &arr) {
        int result = 0;
        // arr is guaranteed to be a mountain array
        // so we don't need to consider if the peak index is 0 or arr.size() - 1
        for (int left = 0, right = arr.size(); left < right;) {
            int mid = (left + right) / 2;

            arr[mid] < arr[mid + 1] ? left = mid + 1 : right = mid;
            result = left;
        }

        return result;
    }
};