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 to A[k], and then monotonically decreases from A[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)
21

1import 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}
35

1function 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}
44

1#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

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Introduction

DFS on Tree

Binary Search Tree

Combinatorial Search

Memoization

Pruning

Dedup

Additional Practices

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Sequence

Grid

Dynamic number of subproblems

Partition

Interval

Two Sequences

Game Theory

0-1 Knapsack

Bitmask

Tree

Introduction

Generalized

Binary Search

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Line Sweep

Tree Traversal without Recursion

Greedy

Composite Patterns

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

The Peak of a Mountain Array

Try it yourself

Explanation