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: .


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 Trues, 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.