You are given an integer mountain array arr
of length n
where the values increase to a peak element and then decrease. Your task is to find the index of the peak element in the array. The peak element is defined as the element which is greater than both of its neighbors.
Constraints:
3 <= arr.length <= 10^5
0 <= arr[i] <= 10^6
arr
is guaranteed to be a mountain array.Your solution must have O(log(n))
time complexity.
Examples:
arr = [0,1,0]
Output: 1
arr = [0,2,1,0]
Output: 1
arr = [0,10,5,2]
Output: 1
Can you implement an algorithm to efficiently find the index of the peak element in the mountain array?
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force strategy for finding the peak in a mountain essentially looks at every single spot to see if it is the highest point. We check each position by comparing it to its neighbors, one at a time, until we find the peak.
Here's how the algorithm would work step-by-step:
def find_peak_in_mountain_array_brute_force(mountain):
array_length = len(mountain)
# Check if the first element is the peak
if mountain[0] > mountain[1]:
return 0
for current_index in range(1, array_length - 1):
# This condition checks if the current element is greater than its neighbors
if mountain[current_index] > mountain[current_index - 1] and \
mountain[current_index] > mountain[current_index + 1]:
return current_index
# Check if the last element is the peak
if mountain[array_length - 1] > mountain[array_length - 2]:
return array_length - 1
return -1 #Should not happen if input is a mountain array
We're trying to find the highest point in a sequence of numbers that goes up and then down. Instead of checking every number, we'll use a clever strategy to quickly narrow down our search.
Here's how the algorithm would work step-by-step:
def peak_index_in_mountain_array(arr):
start_index = 0
end_index = len(arr) - 1
while start_index < end_index:
middle_index = (start_index + end_index) // 2
# Check if middle element is the peak
if arr[middle_index] > arr[middle_index - 1] and arr[middle_index] > arr[middle_index + 1]:
return middle_index
# If middle element is smaller than the next element,
# peak is in the right half
if arr[middle_index] < arr[middle_index + 1]:
start_index = middle_index + 1
# Otherwise, the peak is in the left half
else:
end_index = middle_index
return start_index
Case | How to Handle |
---|---|
Null or empty array | Throw an IllegalArgumentException or return -1, indicating invalid input. |
Array with only one element | Throw an IllegalArgumentException or return -1, as a mountain array requires at least three elements. |
Array with only two elements | Throw an IllegalArgumentException or return -1, as a mountain array requires at least three elements. |
Array where the peak is the first element | The binary search should naturally converge to the correct index in this case as left boundary is never the peak. |
Array where the peak is the last element | The binary search should naturally converge to the correct index in this case as right boundary is never the peak. |
Array with a very large number of elements (performance considerations) | Binary search ensures logarithmic time complexity, scaling well with large inputs. |
Array containing negative numbers or zeros | The binary search approach works regardless of whether the numbers are negative or zero, as it relies on the increasing/decreasing property. |
Integer overflow when calculating the middle index for very large arrays | Calculate the middle index using mid = left + (right - left) / 2 to prevent overflow. |