852. Peak Index in a Mountain Array

Problem

Let's call 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 an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

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

Example 4:

Input: arr = [3,4,5,1]
Output: 2

Example 5:

Input: arr = [24,69,100,99,79,78,67,36,26,19]
Output: 2

Constraints:

• 3 <= arr.length <= 104
• 0 <= arr[i] <= 106
• arr is guaranteed to be a mountain array.

Discussion

The problem setup is a very typical binary search problem. Instead of simply iterate the input and find the peak value, we aim to perform better with binary search approach.

With a common binary search setup, we compare the mid value in each iteration. If the mid value is in rising-side, we search in the later part of the array, else search in the beginning part.

Solution

We begin with a common binary search setup: initializing head and tail, and try to evaluate and the median value, and update the search area in each iteration, until head and tail come across each other.

When mid is smaller than the next value, it's clear in the rising-side, and we search in the later part of the array. Else, we search in the beginning part of the array.

from typing import List

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        head, tail = 0, len(arr) - 1

        while head < tail:
            mid = (head + tail) // 2
            if arr[mid] < arr[mid + 1]:
                head = mid + 1
            else:
                tail = mid

        return head

Complexity Analysis

• Time Complexity: O(log(n)), for simple binary search problem.
• Space Complexity: O(1), as only 3 variables are cached in memory.