Peak Index Locator — Problem Statement & Solution Guide
Problem Description
Given a non-empty array of integers mountainSequence, where the sequence initially strictly increases and then strictly decreases, find the index of the peak element.
Examples
Input
[1, 2, 3, 4, 5, 4, 3, 2, 1]
Output
4
Explanation: Step-by-step: Given the input array [1, 2, 3, 4, 5, 4, 3, 2, 1], we first find the length of the array. Then, we initialize two pointers, one at the start and one at the end of the array. We then enter a loop where we compare the elements at the start and end pointers. If the element at the start pointer is greater than the element at the end pointer, we move the end pointer one step to the left. If the element at the start pointer is less than the element at the end pointer, we move the start pointer one step to the right. We continue this process until the start and end pointers meet. At this point, the start pointer will be pointing to the peak element. We then return the index of the peak element, which is 4.
Input
[1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
Output
0
Explanation: Step-by-step: Given the input array [1, 2, 3, 4, 5, 4, 3, 2, 1, 0], we first find the length of the array. Since the array has only one element, we can directly return 0 as the index of the peak element.
Constraints
- 1 <= array length <= 10^5
- Array represents a mountain sequence
- All elements are distinct integers
- Array is not empty
- Only one peak element exists
Optimal Approach & Strategy
The optimal approach is to use a modified binary search algorithm, which takes advantage of the mountain sequence structure to find the peak element in O(log n) time complexity. This approach divides the search space in half at each step.
Brute Force Approach
A naive approach would be to iterate through the array and check each element to see if it's the peak, resulting in an O(n) time complexity. This can be improved upon. The brute force approach is not efficient for large arrays.
Verified Code Solutions
function findPeakIndex(mountainSequence) { if (mountainSequence.length === 0) return -1; if (mountainSequence.length === 1) return 0; let left = 0, right = mountainSequence.length - 1; while (left < right) { let mid = Math.floor((left + right) / 2); if (mountainSequence[mid] < mountainSequence[mid + 1]) left = mid + 1; else right = mid; } return left === 0 ? 0 : left - 1; }class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > arr[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}def peakIndexInMountainArray(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] > arr[mid + 1]:
right = mid
else:
left = mid + 1
return leftfunction findPeakIndex(mountainSequence) { if (mountainSequence.length === 0) return -1; if (mountainSequence.length === 1) return 0; let left = 0, right = mountainSequence.length - 1; while (left < right) { let mid = Math.floor((left + right) / 2); if (mountainSequence[mid] < mountainSequence[mid + 1]) left = mid + 1; else right = mid; } return left === 0 ? 0 : left - 1; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.