Get started

Peak Index in a Mountain Array — Medium Problem & Solution

arr is a mountain array: it strictly increases to a single peak and then strictly decreases, with the peak neither first nor last.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Meta, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

arr is a mountain array: it strictly increases to a single peak and then strictly decreases, with the peak neither first nor last.

Return the index of the peak in O(log n) time.

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 <= 100000
  • 0 <= arr[i] <= 1000000
  • arr is a mountain array.

How to solve Peak Index in a Mountain Array

The array has no target to search for, but it does have a monotone predicate: 'still ascending at index i'. That is true for every index before the peak and false from the peak onwards, so binary search finds the boundary.

Approach

  1. Maintain lo and hi over the candidate indices.
  2. If arr[mid] < arr[mid + 1], the peak lies after mid, so lo = mid + 1.
  3. Otherwise the peak is at mid or before it, so hi = mid.

Why it works

Because the array strictly increases then strictly decreases, arr[i] < arr[i+1] holds exactly for i below the peak. Binary searching that boolean converges on the first index where it fails, which is the peak. The mountain guarantee is what makes mid + 1 always a valid index inside the loop.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Setting hi = mid - 1 can skip past the peak, since mid is still a candidate.
  • Comparing with the left neighbour needs a different boundary and is easier to get wrong.
  • A linear scan is O(n) and misses the stated requirement.

Reference solution

Python

from typing import List

def peakIndexInMountainArray(arr: List[int]) -> int:
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < arr[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

JavaScript

var peakIndexInMountainArray = function(arr) {
    var lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (arr[mid] < arr[mid + 1]) lo = mid + 1; else hi = mid;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue