Peak Index in a Mountain Array - Solution & Explanation
Problem Statement
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.
Approach Overview
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 1: Binary Search Approach
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.
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.
Complexity
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.
Approach 2: Linear Scan Approach
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.
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.
Complexity
Time complexity: O(n) as each element is visited once.
Space complexity: O(1).
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time complexity: |
| Linear Scan Approach | Time complexity: |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Peak Index in Mountain Array | Binary Search | Leetcode 852 • Apna College • 208,032 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Peak Index in a Mountain Array easy or hard?
Peak Index in a Mountain Array Python/Java solution
How to solve Peak Index in a Mountain Array in O(n)?
What is the best approach for Peak Index in a Mountain Array?
Is Peak Index in a Mountain Array asked at Google/Amazon/Meta?
What data structure is used in Peak Index in a Mountain Array?
What is the time complexity of Peak Index in a Mountain Array?
Ready to solve this problem?
Practice Peak Index in a Mountain Array with our built-in code editor and test cases.
Practice on FleetCode