Solution Approach

The solution uses the standard binary search template to find the first index where arr[i] > arr[i + 1].

Implementation using the standard template:

left, right = 1, len(arr) - 2
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if arr[mid] > arr[mid + 1]:  # feasible condition: at or past peak
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

Step-by-step breakdown:

1. Initialize: Set left = 1, right = len(arr) - 2, and first_true_index = -1. We exclude boundary indices since they cannot be peaks.

2. Define the feasible condition: arr[mid] > arr[mid + 1] means we're at the peak or on the descending slope.

3. Binary search loop (while left <= right):

   • Calculate mid = (left + right) // 2
   • If feasible (arr[mid] > arr[mid + 1]): save first_true_index = mid, then search left (right = mid - 1)
   • If not feasible: search right (left = mid + 1)

4. Return: first_true_index contains the peak index.

Why this works:

• The feasible condition creates a [false, false, ..., true, true, ...] pattern
• When we find a true, we save it and search left for an even smaller true
• When we find a false, we search right
• The final first_true_index is the smallest index where the condition holds - the peak

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, right = 3, first_true_index = -1
• Feasible condition: arr[mid] > arr[mid + 1]

Iteration 1:

• left = 1, right = 3
• Calculate mid = (1 + 3) // 2 = 2
• Check feasible: arr[2] > arr[3]? Is 5 > 4? Yes (true)
• Save first_true_index = 2, search left: right = mid - 1 = 1

Iteration 2:

• left = 1, right = 1
• Calculate mid = (1 + 1) // 2 = 1
• Check feasible: arr[1] > arr[2]? Is 3 > 5? No (false)
• Search right: left = mid + 1 = 2

Termination:

• Now left = 2 > right = 1
• The loop exits since left > right
• Return first_true_index = 2

The peak element is at index 2, which contains the value 5. We found it in just 2 comparisons instead of checking all 5 elements.

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. Using the Wrong Binary Search Template

Pitfall: Using while left < right with right = mid instead of the standard template.

Incorrect:

while left < right:
    mid = (left + right) // 2
    if arr[mid] > arr[mid + 1]:
        right = mid
    else:
        left = mid + 1
return left

Correct (using standard template):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if arr[mid] > arr[mid + 1]:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

2. Incorrect Boundary Initialization

Pitfall: Initializing left = 0 and right = len(arr) - 1, which includes boundary elements.

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

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

3. Confusion with Comparison Direction

Pitfall: 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
• It may lead to incorrect identification of which slope we're on

Solution: Consistently compare arr[mid] with arr[mid + 1] for the feasible condition.

4. Handling Edge Cases Incorrectly

Pitfall: Adding special cases for boundary elements.

Example of incorrect assumption:

# Wrong: Trying to handle peaks at boundaries
if arr[0] > arr[1]:
    return 0

Solution: Trust the problem constraints - the peak is never at the boundaries in a valid mountain array.