Peak Index in a Mountain Array
MedPrompt
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
2 approaches with complexity analysis and trade-offs.
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.
Walkthrough
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
Time
O(n), where n is the number of elements in the array. In the worst-case scenario (e.g., `[0, 1, 2, ..., n-2, n-3]`), we might have to traverse almost the entire array to find the peak.
Space
O(1), as we only use a few variables to store the index, requiring constant extra space.
Trade-offs
Pros
Very simple to understand and implement.
Requires no complex logic.
Cons
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.
A more efficient approach that meets the O(log n) time complexity requirement is to use binary search. The properties of the mountain array allow us to discard half of the search space in each step. We can determine whether the middle element is on the ascending or descending slope and adjust our search range accordingly.
Algorithm
- Initialize two pointers,
low = 0andhigh = arr.length - 1. * Loop as long aslow < high. * Calculate the middle index:mid = low + (high - low) / 2. * Check ifarr[mid]is less thanarr[mid + 1]. * If true,midis on the ascending slope. The peak is in the range[mid + 1, high]. Updatelow = mid + 1. * If false,midis on the descending slope or is the peak. The peak is in the range[low, mid]. Updatehigh = mid. * When the loop terminates,lowandhighwill be equal and point to the peak index. Returnlow.
Walkthrough
The core idea is to apply binary search on the array indices. We maintain two pointers, low and high, which define the current search space.
In each step, we calculate the middle index mid. We then compare arr[mid] with its right neighbor arr[mid + 1].
- If
arr[mid] < arr[mid + 1], it meansmidis on the ascending slope of the mountain. The peak must be located to the right ofmid. Therefore, we can safely discard the left half of the search space, includingmid, by settinglow = mid + 1. - If
arr[mid] > arr[mid + 1], it meansmidis either the peak itself or on the descending slope. In this case, the peak is atmidor to its left. We can discard the right half, but we must keepmidin our search space as it could be the peak. We do this by settinghigh = mid. We repeat this process untillowandhighconverge (low == high). The index they converge to is the peak index.
class Solution { public int peakIndexInMountainArray(int[] arr) { int low = 0; int high = arr.length - 1; while (low < high) { int mid = low + (high - low) / 2; if (arr[mid] < arr[mid + 1]) { // We are in the increasing part of the array // The peak is to the right low = mid + 1; } else { // We are in the decreasing part of the array, or at the peak // The peak is at mid or to the left high = mid; } } // low and high will converge to the peak index return low; }}Complexity
Time
O(log n), where n is the length of the array. This is because binary search halves the search space in each iteration.
Space
O(1), as it only requires a few variables for the pointers and the middle index, using constant extra space.
Trade-offs
Pros
Highly efficient and optimal for this problem.
Meets the
O(log n)time complexity requirement.
Cons
Slightly more complex to reason about and implement correctly compared to a linear scan.
Requires careful handling of pointers and boundary conditions to avoid infinite loops or incorrect results.
Solutions
Solution
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; }}/** * @param {number[]} arr * @return {number} */ var peakIndexInMountainArray = function (arr) { let left = 1; let right = arr.length - 2; while (left < right) { const mid = (left + right) >> 1; if (arr[mid] > arr[mid + 1]) { right = mid; } else { left = mid + 1; } } return left; };class Solution {public: int peakIndexInMountainArray(vector<int> &arr) { int left = 1, right = arr.size() - 2; while (left < right) { int mid = (left + right) >> 1; if (arr[mid] > arr[mid + 1]) right = mid; else left = mid + 1; } return left; }};class Solution: def peakIndexInMountainArray(self, arr: List[int]) -> int: left, right = 1, len(arr) - 2 while left < right: mid = (left + right) >> 1 if arr[mid] > arr[mid + 1]: right = mid else: left = mid + 1 return leftVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.