Peak Index in a Mountain Array

Problem Description

You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease. Return the index of the peak element.

Key Insights

• The array is guaranteed to be a mountain array, meaning there is one peak element.
• A peak element is defined as an element that is greater than its neighbors.
• The problem can be efficiently solved using a binary search approach to achieve O(log(n)) time complexity.

Space and Time Complexity

Time Complexity: O(log(n))
Space Complexity: O(1)

Solution

To find the peak index in a mountain array, we can utilize a binary search algorithm. The key idea is to compare the middle element with its neighbors to determine whether we should search in the left half or the right half of the array. If the middle element is less than its right neighbor, it means the peak lies in the right half. Conversely, if it is greater than its right neighbor, the peak must be in the left half or could be the middle element itself.

The algorithm proceeds as follows:

1. Initialize two pointers, left at 0 and right at the last index of the array.
2. While left is less than right, compute the middle index.
3. Compare the middle element with its right neighbor:
   • If the middle element is less than the right neighbor, move the left pointer to mid + 1.
   • Otherwise, move the right pointer to mid.
4. When the loop ends, left will point to the peak element.

Code Solutions