The Peak of a Mountain Array
Prereq: Vanilla Binary Search and Finding the Boundary with Binary Search
A mountain array is defined as an array that
- has at least 3 elements
- has an element with the largest value called "peak", with index
k. The array elements monotonically increase from the first element toA[k], and then monotonically decreases fromA[k + 1]to the last element of the array. Thus creating a "mountain" of numbers.
That is, given A[0]<...<A[k-1]<A[k]>A[k+1]>...>A[n-1], we need to find the index k. Note that the peak element is neither the first nor the last element of the array.
Find the index of the peak element. Assume there is only one peak element.
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 the Boundary module.
Time Complexity: O(log(n))
1from typing import List
2
3def peak_of_mountain_array(arr: List[int]) -> int:
4 left, right = 0, len(arr) - 1
5 boundary_index = -1
6
7 while left <= right:
8 mid = (left + right) // 2
9 if arr[mid] > arr[mid + 1]:
10 boundary_index = mid
11 right = mid - 1
12 else:
13 left = mid + 1
14
15 return boundary_index
16
17if __name__ == '__main__':
18 arr = [int(x) for x in input().split()]
19 res = peak_of_mountain_array(arr)
20 print(res)
211import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int peakOfMountainArray(List<Integer> arr) {
8 int left = 0;
9 int right = arr.size() - 1;
10 int boundaryIndex = -1;
11 while (left <= right) {
12 int mid = left + (right - left) / 2;
13 if (arr.get(mid) > arr.get(mid + 1)) {
14 boundaryIndex = mid;
15 right = mid - 1;
16 } else {
17 left = mid + 1;
18 }
19 }
20 return boundaryIndex;
21 }
22
23 public static List<String> splitWords(String s) {
24 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
25 }
26
27 public static void main(String[] args) {
28 Scanner scanner = new Scanner(System.in);
29 List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
30 scanner.close();
31 int res = peakOfMountainArray(arr);
32 System.out.println(res);
33 }
34}
351using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7 public static int PeakOfMountainArray(List<int> arr)
8 {
9 int left = 0;
10 int right = arr.Count - 1;
11 int boundaryIndex = -1;
12 while (left <= right)
13 {
14 int mid = left + (right - left) / 2;
15 if (arr[mid] > arr[mid + 1])
16 {
17 boundaryIndex = mid;
18 right = mid - 1;
19 }
20 else
21 {
22 left = mid + 1;
23 }
24 }
25 return boundaryIndex;
26 }
27
28 public static List<string> SplitWords(string s)
29 {
30 return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
31 }
32
33 public static void Main()
34 {
35 List<int> arr = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
36 int res = PeakOfMountainArray(arr);
37 Console.WriteLine(res);
38 }
39}
401function peakOfMountainArray(arr) {
2 let left = 0;
3 let right = arr.length - 1;
4 let boundary_index = -1;
5 while (left <= right) {
6 let mid = left + Math.floor((right - left) / 2);
7 if (arr[mid] > arr[mid + 1]) {
8 boundary_index = mid;
9 right = mid - 1;
10 } else {
11 left = mid + 1;
12 }
13 }
14 return boundary_index;
15}
16
17function splitWords(s) {
18 return s == "" ? [] : s.split(' ');
19}
20
21function* main() {
22 const arr = splitWords(yield).map((v) => parseInt(v));
23 const res = peakOfMountainArray(arr);
24 console.log(res);
25}
26
27class EOFError extends Error {}
28{
29 const gen = main();
30 const next = (line) => gen.next(line).done && process.exit();
31 let buf = '';
32 next();
33 process.stdin.setEncoding('utf8');
34 process.stdin.on('data', (data) => {
35 const lines = (buf + data).split('\n');
36 buf = lines.pop();
37 lines.forEach(next);
38 });
39 process.stdin.on('end', () => {
40 buf && next(buf);
41 gen.throw(new EOFError());
42 });
43}
441#include <algorithm> // copy
2#include <iostream> // cin, cout
3#include <iterator> // back_inserter, istream_iterator
4#include <sstream> // istringstream
5#include <string> // getline, string
6#include <vector> // vector
7
8int peak_of_mountain_array(std::vector<int> arr) {
9 int left = 0, right = arr.size() - 1, boundary_index = -1;
10 while (left <= right) {
11 int mid = left + (right - left) / 2;
12 if (arr[mid] > arr[mid + 1]) {
13 boundary_index = mid;
14 right = mid - 1;
15 } else {
16 left = mid + 1;
17 }
18 }
19 return boundary_index;
20}
21
22template<typename T>
23std::vector<T> get_words() {
24 std::string line;
25 std::getline(std::cin, line);
26 std::istringstream ss{line};
27 std::vector<T> v;
28 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
29 return v;
30}
31
32int main() {
33 std::vector<int> arr = get_words<int>();
34 int res = peak_of_mountain_array(arr);
35 std::cout << res << '\n';
36}
37