Peak Index in a Mountain Array
MEDIUMDescription
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.
Your task is to solve it in O(log(n)) time complexity.
Example 1:
Input: arr = [0,1,0]
Output: 1
Example 2:
Input: arr = [0,2,1,0]
Output: 1
Example 3:
Input: arr = [0,10,5,2]
Output: 1
Constraints:
3 <= arr.length <= 1050 <= arr[i] <= 106arris guaranteed to be a mountain array.
Approaches
Checkout 2 different approaches to solve Peak Index in a Mountain Array. Click on different approaches to view the approach and algorithm in detail.
Linear Scan
This approach involves iterating through the array to find the peak element. A peak element is one that is greater than its immediate neighbors. Since the array is guaranteed to be a mountain array (strictly increasing then strictly decreasing), we can find the peak by identifying the first element that is greater than the next one.
Algorithm
- Iterate through the array
arrwith an indexifrom0toarr.length - 2. * In each iteration, check ifarr[i] > arr[i+1]. * If this condition is true, it means we have just passed the peak. The peak is at indexi. Returni.
We can traverse the array from the beginning. The peak is the highest point, so the elements increase up to the peak and then decrease. This means the peak is the first element arr[i] for which arr[i] > arr[i+1]. We can iterate from the first element up to the second-to-last element and check this condition. The first time this condition is met, we have found our peak index and can return it immediately. Because the problem guarantees a mountain array of at least length 3, a peak is guaranteed to exist and will be found by this method.
class Solution {
public int peakIndexInMountainArray(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i+1]) {
return i;
}
}
return -1; // Should not be reached given the problem constraints
}
}
Complexity Analysis
Pros and Cons
- Very simple to understand and implement.
- Requires no complex logic.
- Inefficient for large arrays as it has a linear time complexity.
- Does not meet the
O(log n)time complexity requirement specified in the problem description.
Code Solutions
Checking out 4 solutions in different languages for Peak Index in a Mountain Array. Click on different languages to view the code.
class Solution {
public
int peakIndexInMountainArray(int[] arr) {
int left = 1, right = arr.length - 2;
while (left < right) {
int mid = (left + right) >> 1;
if (arr[mid] > arr[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
Video Solution
Watch the video walkthrough for Peak Index in a Mountain Array
Similar Questions
5 related questions you might find useful
Algorithms:
Data Structures:
Companies:
Subscribe to Scale Engineer newsletter
Learn about System Design, Software Engineering, and interview experiences every week.
No spam, unsubscribe at any time.