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
arrthat 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:
- Initialize two pointers,
leftandright, to the start and end of the array, respectively. - While
leftis less thanright:- Calculate the middle index
mid. - Compare the element at
midwith the element atmid + 1. - If
arr[mid] < arr[mid + 1], it means we are on the increasing part of the mountain, so move theleftpointer tomid + 1. - Otherwise, we are on the decreasing part of the mountain, so move the
rightpointer tomid.
- Calculate the middle index
- When
leftequalsright, 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.