The Peak of a Mountain Array
Prerequisite: 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 strictly increase from the first element toA[k], and then strictly decrease 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 lastIndex 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 array strictly increases until the peak element and then strictly decreases. The monotonicity is a strong sign that we can use binary search to find the peak element.
To use binary search, we need the entire search range to be strictly increasing or decreasing. We need to find the feasible function that returns false for elements up until the peak and true from the peak to the end.
We already know the array strictly decreases from the peak element to the last element. So we can try to use a feasible function of arr[i]> arr[i+1] to return true for elements from the peak to the last element.
Once we do that, we realize that it also returns false from the first element to the peak element. We've got our feasible function.
A minor edge case is the last element, as it has no next element. We can pad the array with an imaginary node of negative infinity.
In the implementation, we don't actually need to pad the array, as that would incur an O(n) extra cost. We can just check if i+1 is out of bounds and return true if it is since this implies arr[i] is the last element.
Now, the problem is reduced to finding the first true element in a boolean array, and we already know how to do this from the Finding the First True in a Sorted Boolean Array module.
Time Complexity: O(log(n))
Space Complexity: O(1)
1def peak_of_mountain_array(arr: list[int]) -> int:
2 alen = len(arr)
3 left = 0
4 right = alen - 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 alen = arr.size();
9 int left = 0;
10 int right = alen - 1;
11 int boundaryIndex = -1;
12 while (left <= right) {
13 int mid = left + (right - left) / 2;
14 if (arr.get(mid) > arr.get(mid + 1)) {
15 boundaryIndex = mid;
16 right = mid - 1;
17 } else {
18 left = mid + 1;
19 }
20 }
21 return boundaryIndex;
22 }
23
24 public static List<String> splitWords(String s) {
25 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
26 }
27
28 public static void main(String[] args) {
29 Scanner scanner = new Scanner(System.in);
30 List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
31 scanner.close();
32 int res = peakOfMountainArray(arr);
33 System.out.println(res);
34 }
35}
361using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7 public static int PeakOfMountainArray(List<int> arr)
8 {
9 int alen = arr.Count;
10 int left = 0;
11 int right = alen - 1;
12 int boundaryIndex = -1;
13 while (left <= right)
14 {
15 int mid = left + (right - left) / 2;
16 if (arr[mid] > arr[mid + 1])
17 {
18 boundaryIndex = mid;
19 right = mid - 1;
20 }
21 else
22 {
23 left = mid + 1;
24 }
25 }
26 return boundaryIndex;
27 }
28
29 public static List<string> SplitWords(string s)
30 {
31 return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
32 }
33
34 public static void Main()
35 {
36 List<int> arr = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
37 int res = PeakOfMountainArray(arr);
38 Console.WriteLine(res);
39 }
40}
411"use strict";
2
3function peakOfMountainArray(arr) {
4 const alen = arr.length;
5 let left = 0;
6 let right = alen - 1;
7 let boundaryIndex = -1;
8 while (left <= right) {
9 const mid = left + Math.floor((right - left) / 2);
10 if (arr[mid] > arr[mid + 1]) {
11 boundaryIndex = mid;
12 right = mid - 1;
13 } else {
14 left = mid + 1;
15 }
16 }
17 return boundaryIndex;
18}
19
20function splitWords(s) {
21 return s === "" ? [] : s.split(" ");
22}
23
24function* main() {
25 const arr = splitWords(yield).map((v) => parseInt(v));
26 const res = peakOfMountainArray(arr);
27 console.log(res);
28}
29
30class EOFError extends Error {}
31{
32 const gen = main();
33 const next = (line) => gen.next(line).done && process.exit();
34 let buf = "";
35 next();
36 process.stdin.setEncoding("utf8");
37 process.stdin.on("data", (data) => {
38 const lines = (buf + data).split("\n");
39 buf = lines.pop();
40 lines.forEach(next);
41 });
42 process.stdin.on("end", () => {
43 buf && next(buf);
44 gen.throw(new EOFError());
45 });
46}
471function peakOfMountainArray(arr: number[]): number {
2 const alen = arr.length;
3 let left = 0;
4 let right = alen - 1;
5 let boundaryIndex = -1;
6 while (left <= right) {
7 const mid = left + Math.floor((right - left) / 2);
8 if (arr[mid] > arr[mid + 1]) {
9 boundaryIndex = mid;
10 right = mid - 1;
11 } else {
12 left = mid + 1;
13 }
14 }
15 return boundaryIndex;
16}
17
18function splitWords(s: string): string[] {
19 return s === "" ? [] : s.split(" ");
20}
21
22function* main() {
23 const arr = splitWords(yield).map((v) => parseInt(v));
24 const res = peakOfMountainArray(arr);
25 console.log(res);
26}
27
28class EOFError extends Error {}
29{
30 const gen = main();
31 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
32 let buf = "";
33 next();
34 process.stdin.setEncoding("utf8");
35 process.stdin.on("data", (data) => {
36 const lines = (buf + data).split("\n");
37 buf = lines.pop() ?? "";
38 lines.forEach(next);
39 });
40 process.stdin.on("end", () => {
41 buf && next(buf);
42 gen.throw(new EOFError());
43 });
44}
451#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int peak_of_mountain_array(std::vector<int> arr) {
9 int alen = arr.size();
10 int left = 0;
11 int right = alen - 1;
12 int boundary_index = -1;
13 while (left <= right) {
14 int mid = left + (right - left) / 2;
15 if (arr[mid] > arr[mid + 1]) {
16 boundary_index = mid;
17 right = mid - 1;
18 } else {
19 left = mid + 1;
20 }
21 }
22 return boundary_index;
23}
24
25template<typename T>
26std::vector<T> get_words() {
27 std::string line;
28 std::getline(std::cin, line);
29 std::istringstream ss{line};
30 ss >> std::boolalpha;
31 std::vector<T> v;
32 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
33 return v;
34}
35
36int main() {
37 std::vector<int> arr = get_words<int>();
38 int res = peak_of_mountain_array(arr);
39 std::cout << res << '\n';
40}
411package main
2
3import (
4 "bufio"
5 "fmt"
6 "os"
7 "strconv"
8 "strings"
9)
10
11func peakOfMountainArray(arr []int) int {
12 alen := len(arr)
13 left := 0
14 right := alen - 1
15 boundaryIndex := -1
16
17 for left <= right {
18 mid := (left + right) / 2
19 if arr[mid] > arr[mid+1] {
20 boundaryIndex = mid
21 right = mid - 1
22 } else {
23 left = mid + 1
24 }
25 }
26 return boundaryIndex
27}
28
29func arrayAtoi(arr []string) []int {
30 res := []int{}
31 for _, x := range arr {
32 v, _ := strconv.Atoi(x)
33 res = append(res, v)
34 }
35 return res
36}
37
38func splitWords(s string) []string {
39 if s == "" {
40 return []string{}
41 }
42 return strings.Split(s, " ")
43}
44
45func main() {
46 scanner := bufio.NewScanner(os.Stdin)
47 scanner.Scan()
48 arr := arrayAtoi(splitWords(scanner.Text()))
49 res := peakOfMountainArray(arr)
50 fmt.Println(res)
51}
52