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] <= 106arr is guaranteed to be a mountain array.In #852 Peak Index in a Mountain Array, the array follows a special structure: values strictly increase up to a peak and then strictly decrease. The goal is to find the index of this peak element efficiently.
A straightforward idea is a linear scan, checking where the sequence changes from increasing to decreasing. While simple, this takes O(n) time.
A more optimal approach leverages Binary Search. Since the array forms a mountain shape, we can compare arr[mid] with arr[mid + 1]. If the next value is larger, the peak lies on the right; otherwise, it lies on the left (including mid). Repeating this process gradually narrows the search space until the peak index is found.
This technique uses the sorted-like structure of the mountain slope, reducing the search range each step and achieving logarithmic time complexity with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Linear Scan | O(n) | O(1) |
| Binary Search (Optimal) | O(log n) | O(1) |
NeetCodeIO
This approach leverages the characteristics of a mountain array to achieve an O(log n) time complexity using binary search. The concept is to look for the part of the array where the increase turns into a decrease. We will perform a binary search for the peak index by comparing middle elements and deciding the side that can have the peak element.
Time complexity: O(log n) since we are performing a binary search.
Space complexity: O(1) as we are using a constant amount of extra space.
1function peakIndexInMountainArray(arr) {
2 let low = 0, high = arr.length - 1;
3 while (low < high) {
4
The JavaScript solution deploys binary search by iterating as long as low is different from high. It computes mid and compares arr[mid] with arr[mid + 1], adjusting search bounds based on this comparison.
This approach involves a simple linear scan to find the peak element. Although not achieving the necessary O(log n) time complexity, it serves as a straightforward solution to verify correctness.
Time complexity: O(n) as each element is visited once.
Space complexity: O(1).
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Binary search works because the array has a predictable structure: strictly increasing then strictly decreasing. This property allows you to determine the direction of the peak by comparing adjacent values and narrowing the search space.
Yes, variations of this problem are common in technical interviews, including FAANG-style interviews. It tests understanding of binary search patterns and the ability to exploit structured arrays.
The problem primarily uses an array. The key idea is not a special data structure but leveraging the mountain array property with binary search to efficiently locate the peak.
The optimal approach uses binary search. By comparing the middle element with its next element, you can determine which side of the mountain the peak lies on and shrink the search range until the peak index is found.
In Java, the solution uses a loop starting from the second element up to the second-last, checking each to ensure it's greater than its neighbors. If a peak is located, its index is returned.