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)

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;
    }
};