Problem 38.1 · Advanced Search and Divide & ConquerMedium

Peak Index in a Mountain Array

PatternBinary Search on an Index Divide and Conquer

What it teaches: Search on the slope instead of a value.

Practise it on judges as “Peak Index in a Mountain Array”.

In plain words

You are walking along a mountain path: it only goes up, reaches the top, then only goes down. Look at any spot and the next step: if the next step is higher, you are still climbing, so the top is to the right; if it is lower, you are past the top or on it. Each look throws away half the path.

Return the index of the top. Example: arr = [0, 10, 5, 2] → 1.

The problem

The array strictly increases to one peak and then strictly decreases. Return the peak's index in O(log n).

Example 1

Input: arr = [0, 10, 5, 2]
Output: 1

Constraints

3 ≤ n ≤ 10⁵

Pattern clues in the wording

→ Unimodal array
→ O(log n) required

These clues point to Binary Search on an Index: In sorted data, check the middle and throw away the half that can't contain the answer.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	arr = [0,1,0]	1
2	arr = [0,2,1,0]	1
3	arr = [0,10,5,2]	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Binary search on the slope · O(log n)

Binary search on the slope

Time O(log n) Space O(1)

Rising at mid → peak is right of mid; otherwise mid or left.

▶ Dry run: Follow the slope uphillarr = [0, 10, 5, 2]

↑lo

↑mid

↑hi

Step 1/3mid = 1. arr[1] = 10 is bigger than arr[2] = 5: we are going downhill, so the top is at mid or to its left. hi = 1.

Approach 1

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

Verdict: The discrete ternary search.

Before you submit

Edge cases and common mistakes

Test these inputs

Peak at index 1
Peak at n − 2

Mistakes people make

Comparing with arr[mid − 1] and going out of bounds at mid = 0.

Interview

Follow-up questions

What if the array has several local peaks (Find Peak Element)?

Command Palette

The problem

Approaches

Binary search on the slope

Edge cases and common mistakes

Follow-up questions