Watch 10 video solutions for Peak Index in a Mountain Array, a medium level problem involving Array, Binary Search. This walkthrough by Apna College has 178,616 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You are given a mountain array where elements strictly increase up to a peak and then strictly decrease. The task is to return the index of that peak element. Because the array has a guaranteed increasing and then decreasing structure, you can either scan linearly to detect the turning point or exploit the structure using binary search to locate the peak faster.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest solution walks through the array from left to right and checks where the increasing pattern breaks. Iterate from index 1 to n-2 and look for the first index where arr[i] > arr[i-1] and arr[i] > arr[i+1]. That index is the peak. Another equivalent observation is that once arr[i] > arr[i+1] occurs for the first time, i must be the peak since the array strictly increases before the peak and strictly decreases after it. This approach uses only a single pass over the array, making it easy to implement and perfectly acceptable for moderate input sizes.
Approach 2: Binary Search (O(log n) time, O(1) space)
The mountain property makes this problem ideal for binary search. Instead of searching for an exact value, you search for the point where the slope changes from increasing to decreasing. Pick a midpoint mid and compare arr[mid] with arr[mid + 1]. If arr[mid] < arr[mid + 1], you are on the ascending side of the mountain, so the peak must lie to the right. Move left = mid + 1. Otherwise, you are on the descending slope or at the peak, so move right = mid. Continue narrowing the search range until left == right, which points to the peak index.
This works because the array forms a monotonic pattern around the peak: strictly increasing before it and strictly decreasing after it. Binary search repeatedly halves the search space based on slope direction, which reduces the time complexity to logarithmic while keeping constant extra memory.
Recommended for interviews: Start by explaining the linear scan since it shows you recognize the peak property and can solve the problem with a straightforward pass. Then move to the binary search optimization. Interviewers typically expect the binary search solution because it leverages the mountain structure and achieves O(log n) time complexity, demonstrating stronger algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Simple implementation when input size is small or when binary search reasoning is unnecessary |
| Binary Search | O(log n) | O(1) | Optimal approach for large arrays; leverages the mountain property to cut the search space in half each step |