Problem Description

You are given an integer array arr that represents a mountain array. A mountain array has the following properties:

• The array length n is at least 3
• The values strictly increase from the start until reaching a peak element
• After the peak, the values strictly decrease until the end
• There is exactly one peak element in the array

Your task is to find and return the index of the peak element (the highest value in the array).

For example, in the array [1, 3, 5, 4, 2], the peak element is 5 at index 2.

Constraint: You must solve this problem in O(log(n)) time complexity, which means you cannot simply iterate through the array to find the maximum. Instead, you need to use a more efficient approach like binary search.

The solution uses binary search to efficiently locate the peak. It starts with left = 1 and right = len(arr) - 2 (excluding the first and last elements since they cannot be peaks). At each step, it calculates the middle index and compares arr[mid] with arr[mid + 1]:

• If arr[mid] > arr[mid + 1], we're on the descending slope, so the peak is at mid or to its left
• If arr[mid] < arr[mid + 1], we're on the ascending slope, so the peak is to the right of mid

The search continues until left and right converge to the peak element's index.

Intuition

The key insight is recognizing that a mountain array has a special property: it's divided into two parts - an ascending part and a descending part, with a single peak between them. This structure naturally lends itself to binary search.

Think about what happens when we pick any element in the array and compare it with its neighbor:

• If arr[mid] > arr[mid + 1], we know we're on the descending slope of the mountain. The peak must be at our current position or somewhere to the left.
• If arr[mid] < arr[mid + 1], we're still climbing up the mountain. The peak must be somewhere to the right.

This binary decision at each point allows us to eliminate half of the search space with each comparison, achieving the required O(log(n)) time complexity.

Why can we start with left = 1 and right = len(arr) - 2? Because the first and last elements can never be peaks in a mountain array - the first element only has a neighbor to its right that must be greater, and the last element only has a neighbor to its left that must be greater.

The beauty of this approach is that we don't need to find the actual maximum value - we just need to find the point where the trend changes from increasing to decreasing. Once our search range narrows down to a single element (when left == right), we've found our peak.

Learn more about Binary Search patterns.

Solution Approach

The solution implements a modified binary search algorithm to find the peak element in O(log(n)) time.

Implementation Steps:

1. Initialize search boundaries: Set left = 1 and right = len(arr) - 2. We exclude indices 0 and n-1 because they cannot be peaks in a mountain array by definition.

2. Binary search loop: While left < right, we continue searching:

   • Calculate the middle index: mid = (left + right) >> 1 (using bit shift for efficient division by 2)
   • Compare arr[mid] with arr[mid + 1] to determine which side of the peak we're on

3. Decision logic:

   • If arr[mid] > arr[mid + 1]: We're on the descending part of the mountain. The peak is either at mid or to its left. Update right = mid (keeping mid in the search range since it could be the peak).
   • If arr[mid] < arr[mid + 1]: We're on the ascending part of the mountain. The peak must be to the right of mid. Update left = mid + 1 (excluding mid since it can't be the peak).

4. Return the result: When the loop exits, left == right, pointing to the peak element. Return left.

Why this works:

• Each iteration eliminates half of the remaining search space
• The algorithm converges when the search range contains only one element
• This element must be the peak since we've systematically narrowed down from both sides

Time Complexity: O(log(n)) - we divide the search space in half with each iteration Space Complexity: O(1) - only using a constant amount of extra space for variables

Example Walkthrough

Let's walk through finding the peak in the mountain array [1, 3, 5, 4, 2].

Initial Setup:

• Array: [1, 3, 5, 4, 2] (length = 5)
• left = 1 (index of 3)
• right = 3 (index of 4)
• We're searching between indices 1 and 3, excluding the first and last elements

Iteration 1:

• left = 1, right = 3
• Calculate mid = (1 + 3) >> 1 = 2
• Compare arr[2] with arr[3]: Is 5 > 4? Yes
• Since arr[mid] > arr[mid + 1], we're on the descending slope
• The peak is at index 2 or to its left
• Update: right = mid = 2

Iteration 2:

• left = 1, right = 2
• Calculate mid = (1 + 2) >> 1 = 1
• Compare arr[1] with arr[2]: Is 3 > 5? No
• Since arr[mid] < arr[mid + 1], we're on the ascending slope
• The peak must be to the right of index 1
• Update: left = mid + 1 = 2

Termination:

• Now left = 2 and right = 2
• The loop exits since left == right
• Return left = 2

The peak element is at index 2, which contains the value 5. Notice how we found it in just 2 comparisons instead of checking all 5 elements, demonstrating the efficiency of the binary search approach.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n), where n is the length of the input array. The algorithm uses binary search to find the peak element. In each iteration, the search space is reduced by half. Starting with n-2 elements (excluding the first and last elements), the algorithm performs at most log₂(n-2) iterations, which simplifies to O(log n).

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for the variables left, right, and mid, regardless of the input size. No additional data structures are created that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Initialization

A frequent mistake is initializing the search boundaries as left = 0 and right = len(arr) - 1, which includes the first and last elements. This can lead to incorrect results or index out of bounds errors when checking arr[mid + 1].

Why it's problematic:

• If mid equals len(arr) - 1, then arr[mid + 1] causes an IndexError
• The first and last elements cannot be peaks in a valid mountain array by definition

Solution: Always initialize with left = 1 and right = len(arr) - 2 to exclude edge elements.

2. Wrong Update Logic for Search Boundaries

Another common error is incorrectly updating the search boundaries, particularly setting right = mid - 1 when arr[mid] > arr[mid + 1].

Why it's problematic:

• When arr[mid] > arr[mid + 1], we know we're on the descending slope, but mid itself could be the peak
• Setting right = mid - 1 would exclude the potential peak from the search range

Solution: Use right = mid (not mid - 1) when on the descending slope to keep mid in the search range.

3. Confusion with Comparison Direction

Developers sometimes mix up the comparison logic, checking arr[mid] < arr[mid - 1] instead of arr[mid] < arr[mid + 1].

Why it's problematic:

• Comparing with arr[mid - 1] requires different boundary logic and can complicate the algorithm
• It may lead to incorrect identification of which slope we're on

Solution: Consistently compare arr[mid] with arr[mid + 1] to determine if we're ascending or descending.

4. Handling Edge Cases Incorrectly

Not considering arrays with minimum length (n = 3) or assuming the peak could be at the boundaries.

Example of incorrect assumption:

# Wrong: Trying to handle peaks at boundaries
if arr[0] > arr[1]:
    return 0
if arr[-1] > arr[-2]:
    return len(arr) - 1

Solution: Trust the problem constraints - the peak is never at the boundaries in a valid mountain array, so no special edge case handling is needed.