The Peak of Mountain Array

Prereq: Vanilla Binary Search and Finding Boundary with Binary Search

A mountain array is defined as an array that

  • has at least 3 elements
  • let's call the element with the largest value the "peak", with index k. The array elements monotonically increase from the first element to A[k], and then monotonically decreases from A[k + 1] to the last element of the array. Thus creating a "mountain" of numbers.

Find the index of the peak element. Assume there is no duplicate.

Input: 0 1 2 3 2 1 0

Output: 3

Explanation: the largest element is 3 and its index is 3.

Try it yourself

Explanation

The peak element is always larger than the next element. Applying the filter of arr[i] > arr[i + 1] we get a boolean array. A minor edge case is for the last element as it has no next element. In that case, we assume its next element is negative infinity.

Now the problem is reduced to finding the first true element in a boolean array. And we already know how to do this from Find Boundary module.

Time Complexity: O(log(n))

1
1
from typing import List
2
2
3
3
def peak_of_mountain_array(arr: List[int]) -> int:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
4
+
    left, right = 0, len(arr) - 1
5
-
    return 0
5
+
    boundary_index = -1
6
6
7
7
8
+
    while left <= right:
9
+
        mid = (left + right) // 2
10
+
        if mid == len(arr) - 1 or arr[mid] >= arr[mid + 1]:
11
+
            boundary_index = mid
12
+
            right = mid - 1
13
+
        else:
14
+
            left = mid + 1
15
+
16
+
    return boundary_index
17
+
8
18
if __name__ == '__main__':
9
19
    arr = [int(x) for x in input().split()]
10
20
    res = peak_of_mountain_array(arr)
11
21
    print(res)