MediumArrayBinary Search

Peak Index in a Mountain Array

2 approaches, code in every language

A mountain array is one that strictly climbs up to a single summit and then strictly slides back down. Given such an array, report the index of that summit, the position where the values stop increasing and begin decreasing.

Since the shape guarantees exactly one peak and no flat stretches, you can steer toward it by checking the slope at the midpoint rather than examining every entry.

Example 1

Input: arr = [0,2,1,0]

Output: 1

Values rise to 2 at index 1 and fall afterward, so the peak index is 1.

Example 2

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

Output: 1

The largest value 10 sits at index 1, which is the summit.

Constraints

3 ≤ arr.length ≤ 10^5
0 ≤ arr[i] ≤ 10^6
arr is guaranteed to be a valid mountain array

Linear Scan

Walk forward until the sequence stops increasing; the last rising position is the peak.

Loading animation…

Intuition

Because the array strictly ascends and then strictly descends, the first index where the value drops below its predecessor marks the point just past the summit. Scanning left to right and catching that first decrease directly locates the peak, even though it inspects up to every element.

Algorithm walkthrough

1Start comparing from the second element onward.
2At each step, check whether the current value is smaller than the one before it.
3The first time that happens, the previous index was the peak, so return it.
4If no drop is ever seen, the array kept rising, so the last index is the peak.

Implementation

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        for i in range(1, len(arr)):
            if arr[i] < arr[i - 1]:
                return i - 1
        return len(arr) - 1

Time

O(n)

Space

O(1)

Simple, but ignores the logarithmic opportunity the mountain shape offers.

Binary Search on the Slope

Use the direction of the slope at the midpoint to decide which side the peak is on.

Loading animation…

Intuition

At any midpoint, comparing it with its right neighbor tells us whether we are still climbing or already falling. If the next element is larger we are on the ascending face and the peak lies to the right; otherwise we are on the descending face and the peak is at mid or to its left. Repeatedly applying this halves the range until only the summit remains.

Algorithm walkthrough

1Initialize lo at the first index and hi at the last index.
2While lo is less than hi, take the midpoint.
3If arr[mid] is smaller than arr[mid + 1], we are still ascending, so move lo to mid + 1.
4Otherwise the peak is at mid or earlier, so set hi to mid.
5When lo meets hi, that index is the summit.

Implementation

class Solution:
    def peakIndexInMountainArray(self, 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

Time

O(log n)

Space

O(1)

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Kiln Ramp Peak is our own problem on the technique behind Peak Index in a Mountain Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free