Approach 1: Linear Scan
Intuition and Algorithm
The mountain increases until it doesn't. The point at which it stops increasing is the peak.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Approach 2: Binary Search
Intuition and Algorithm
The comparison A[i] < A[i+1]
in a mountain array looks like [True, True, True, ..., True, False, False, ..., False]
: 1 or more boolean True
s, followed by 1 or more boolean False
. For example, in the mountain array [1, 2, 3, 4, 1]
, the comparisons A[i] < A[i+1]
would be True, True, True, False
.
We can binary search over this array of comparisons, to find the largest index i
such that A[i] < A[i+1]
. For more on binary search, see the LeetCode explore topic here.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.