Peak Index in a Mountain Array

Medium
823.

Peak Index in a Mountain Array

Peak Index in a Mountain Array is a medium coding problem on arrays and binary search, asked in Amazon, Meta and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Peak Index in a Mountain Array — Problem & Solution

Peak Index in a Mountain Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Peak Index in a Mountain Array is a medium coding problem on arrays and binary search, asked in Amazon, Meta and Infosys interviews.

  • 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.

Hints for Peak Index in a Mountain Array

  1. Hint 1

    Compare each midpoint with its right neighbour rather than with a target.

  2. Hint 2

    arr[mid] < arr[mid + 1] means you are still climbing — the peak is strictly to the right.

  3. Hint 3

    Otherwise mid could itself be the peak, so keep it in the range.

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

Java

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

C++

int peakIndexInMountainArray(vector<int>& arr) {
    int lo = 0, hi = (int) arr.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search