Domain 1EasyCORE

Peak Index in a Mountain Array

The problem asks us to find the peak index in a mountain array. A mountain array is defined as an array that first strictly increases to a peak element and then strictly decreases. The input is guaranteed to be a valid mountain array with at least 3 elements. The output should be the index of the peak element.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Binary Search

852. Peak Index in a Mountain Array

Model: qwen2.5-coder:14b
Topics: Binary Search
FAANG asked: 0
Acceptance rate: 71.8%


Problem Breakdown

The problem asks us to find the peak index in a mountain array. A mountain array is defined as an array that first strictly increases to a peak element and then strictly decreases. The input is guaranteed to be a valid mountain array with at least 3 elements. The output should be the index of the peak element.

Inputs:

  • An integer array arr that is guaranteed to be a mountain array.

Outputs:

  • An integer representing the index of the peak element in the array.

Implicit Constraints and Edge Cases:

  • The array length is at least 3.
  • There are no duplicates in the array.
  • All elements are non-negative integers.

Intuition

A brute-force approach would involve iterating through the array to find the peak element, which would have a time complexity of O(n). However, since the array is guaranteed to be a mountain array, we can leverage this property to achieve a more efficient solution with binary search. The key insight is that at any point in the array, if the current element is less than the next element, we are still climbing the mountain and should move towards the right half of the array. Conversely, if the current element is greater than the next element, we have passed the peak and should move towards the left half.

Approach

We will use binary search to find the peak index in O(log(n)) time complexity. The steps are as follows:

  1. Initialize two pointers, left and right, to the start and end of the array, respectively.
  2. While left is less than right:
    • Calculate the middle index mid.
    • Compare the element at mid with the element at mid + 1.
    • If arr[mid] < arr[mid + 1], it means we are on the increasing part of the mountain, so move the left pointer to mid + 1.
    • Otherwise, we are on the decreasing part of the mountain, so move the right pointer to mid.
  3. When left equals right, we have found the peak index.

Complexity Analysis

  • Time Complexity: O(log(n)) because we are using binary search to reduce the search space by half in each iteration.
  • Space Complexity: O(1) as we are using a constant amount of extra space for the pointers.

Solution

def peakIndexInMountainArray(arr):
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if arr[mid] < arr[mid + 1]:
            left = mid + 1
        else:
            right = mid
    
    return left

Edge Cases Handled

  • The array is guaranteed to be a mountain array, so no need to handle invalid input cases.
  • The binary search ensures that we efficiently find the peak index even for large arrays.