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.
1class Solution {
2 public int peakIndexInMountainArray(int[] arr) {
3 int low = 0, high = arr.length - 1;
4
This Java solution replicates the binary search strategy to find the peak in a mountain array. We initialize low as 0 and high as the last index of the array, iterating until they meet. The peak index is found by leveraging comparisons within the loop.
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).
1using System;
public class Solution {
public int PeakIndexInMountainArray(int[] arr) {
for (int i = 1; i < arr.Length - 1; ++i) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
return i;
}
}
return -1; // This should never be reached according to problem constraints.
}
public static void Main() {
Solution sol = new Solution();
int[] arr = {0, 2, 1, 0};
Console.WriteLine("Peak Index: " + sol.PeakIndexInMountainArray(arr));
}
}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.
C# uses a straightforward for loop from the second element to the second last, checking for the peak condition. The index is returned upon meeting the condition, ensuring correctness due to constraints.