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.
1#include <stdio.h>
2
3int peakIndexInMountainArray(int* arr, int arrSize){
4 int low = 0, high = arrSize - 1;
In this solution, we apply a binary search on the mountain array. The loop continues until low equals high. Each time, we find the mid of the current subarray. If the middle element is less than the next one, it implies the peak is on the right, so we set low to mid + 1. Otherwise, the peak must be at mid or to the left of it, so high is set to mid. The low eventually points to the peak index.
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#include
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.
The C solution performs a linear scan from index 1 to arrSize - 2 (exclusive). For each element, it checks if it is larger than its neighbors. If true, the index is returned as the peak index.