Peak Index in a Mountain Array solution and explanation
Google
TCS
Infosys
9 more videos on this problem
Peak Index in Mountain Array | Binary Search | Leetcode 852Apna College · 23:34 · 208K views
LeetCode Problem: 852. Peak Index in a Mountain Array | Java SolutionCode for Interview · 21:36 · 14K views
Peak Index in a Mountain Array | Binary Search | DRY RUN | GOOGLE | Leetcode-852codestorywithMIK · 19:16 · 14K views
Leetcode 852 Peak Index in a Mountain ArrayJeevan Kumar - Cracckify · 5:33 · 1K views
Peak Index in a Mountain Array - Leetcode 852Algorithms Casts · 8:56 · 666 views
Peak Index in a Mountain Array | Leetcode - 852 | Top Interview Question | Java DSA | GeeksterGeekster · 10:26 · 332 views
Peak Index in a Moutain Array - LeetCode 852 - PythonAlpha-Code · 11:06 · 309 views
852. Peak Index in a Mountain Array Java SolutionCode with Carter · 8:08 · 213 views
852. Peak Index in a Mountain Array (Leetcode Easy)Programming Live with Larry · 10:20 · 196 views
Uncover LeetCode 852. Peak Index in a Mountain Array: Master Binary Search in PythonvanAmsen · 5:53 · 149 views
The problem
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.
def peakIndexInMountainArray(arr):
low, high = 0, len(arr) - 1
while low < high:
mid = (low + high) // 2
if arr[mid] < arr[mid + 1]:
low = mid + 1
else:
high = mid
return low
# Example usage
arr = [0, 2, 1, 0]
print("Peak Index:", peakIndexInMountainArray(arr))class Solution {
public int peakIndexInMountainArray(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {0, 2, 1, 0};
System.out.println("Peak Index: " + sol.peakIndexInMountainArray(arr));
}
}#include <vector>
#include <iostream>
using namespace std;
int peakIndexInMountainArray(vector<int>& arr) {
int low = 0, high = arr.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
int main() {
vector<int> arr = {0, 2, 1, 0};
cout << "Peak Index: " << peakIndexInMountainArray(arr) << endl;
return 0;
}function peakIndexInMountainArray(arr) {
let low = 0, high = arr.length - 1;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Example usage
const arr = [0, 2, 1, 0];
console.log("Peak Index:", peakIndexInMountainArray(arr));#include <stdio.h>
int peakIndexInMountainArray(int* arr, int arrSize){
int low = 0, high = arrSize - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
int main() {
int arr[] = {0, 2, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Peak Index: %d\n", peakIndexInMountainArray(arr, n));
return 0;
}using System;
public class Solution {
public int PeakIndexInMountainArray(int[] arr) {
int low = 0, high = arr.Length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static void Main() {
Solution sol = new Solution();
int[] arr = {0, 2, 1, 0};
Console.WriteLine("Peak Index: " + sol.PeakIndexInMountainArray(arr));
}
}This Python implementation uses a binary search approach. The variables low and high denote the current subarray being examined. During each iteration, the middle index is checked against its next element to decide which half to discard, guiding us to the peak.
Time complexity: O(log n).
Space complexity: O(1).
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.
def peakIndexInMountainArray(arr):
for i in range(1, len(arr) - 1):
if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
return i
return -1 # Should never be reached due to problem constraints
# Example usage
arr = [0, 2, 1, 0]
print("Peak Index:", peakIndexInMountainArray(arr))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 happen due to constraints.
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {0, 2, 1, 0};
System.out.println("Peak Index: " + sol.peakIndexInMountainArray(arr));
}
}#include <vector>
#include <iostream>
using namespace std;
int peakIndexInMountainArray(vector<int>& arr) {
for (int i = 1; i < arr.size() - 1; ++i) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
return i;
}
}
return -1;
}
int main() {
vector<int> arr = {0, 2, 1, 0};
cout << "Peak Index: " << peakIndexInMountainArray(arr) << endl;
return 0;
}function peakIndexInMountainArray(arr) {
for (let 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 due to constraints
}
// Example usage
const arr = [0, 2, 1, 0];
console.log("Peak Index:", peakIndexInMountainArray(arr));#include <stdio.h>
int peakIndexInMountainArray(int* arr, int arrSize){
for (int i = 1; i < arrSize - 1; ++i) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
return i;
}
}
return -1; // Included as a safety net, though problem constraints ensure a peak exists.
}
int main() {
int arr[] = {0, 2, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Peak Index: %d\n", peakIndexInMountainArray(arr, n));
return 0;
}using 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));
}
}In this Python solution, a for loop iterates from the first to the second-to-last element. It checks each element for the peak condition. If found, it returns the index, otherwise continues the scan.
Time complexity: O(n).
Space complexity: O(1).
Approach 3: Default Approach
function peakIndexInMountainArray(arr: number[]): number {
let left = 1,
right = arr.length - 2;
while (left < right) {
const mid = (left + right) >> 1;
if (arr[mid] > arr[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func peakIndexInMountainArray(arr []int) int {
left, right := 1, len(arr)-2
for left < right {
mid := (left + right) >> 1
if arr[mid] > arr[mid+1] {
right = mid
} else {
left = mid + 1
}
}
return left
}impl Solution {
pub fn peak_index_in_mountain_array(arr: Vec<i32>) -> i32 {
let mut left = 1;
let mut right = arr.len() - 2;
while left < right {
let mid = left + (right - left) / 2;
if arr[mid] > arr[mid + 1] {
right = mid;
} else {
left = left + 1;
}
}
left as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time complexity: |
| Linear Scan Approach | Time complexity: |
| Default Approach | – |
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 |
Frequently asked questions
Is Peak Index in a Mountain Array easy or hard?
The problem is rated Medium because recognizing the mountain property and applying binary search on the slope requires some insight. The linear scan version is straightforward, but the expected interview solution is the O(log n) binary search.
Peak Index in a Mountain Array Python/Java solution
Both Python and Java implementations typically use binary search. Maintain two pointers (left and right), compute mid, compare arr[mid] with arr[mid + 1], and move toward the direction where the peak lies. The loop ends when left equals right, which is the peak index.
How to solve Peak Index in a Mountain Array in O(n)?
Use a linear scan across the array. Iterate from left to right and return the first index i where arr[i] > arr[i + 1]. Since the array strictly increases before the peak and decreases afterward, this point must be the peak. The algorithm performs a single pass with O(n) time and constant space.
What is the best approach for Peak Index in a Mountain Array?
Binary search is the best approach because the array strictly increases and then decreases. By comparing arr[mid] with arr[mid + 1], you can determine whether you are on the ascending or descending slope and move the search boundary accordingly. This finds the peak in O(log n) time and O(1) space.
Is Peak Index in a Mountain Array asked at Google/Amazon/Meta?
Peak detection and binary search variations appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests whether you recognize monotonic patterns and apply binary search beyond simple value lookup.
What data structure is used in Peak Index in a Mountain Array?
The problem operates directly on an array. The key technique is binary search over array indices, using element comparisons to determine whether the search should move left or right.
What is the time complexity of Peak Index in a Mountain Array?
The optimal binary search solution runs in O(log n) time with O(1) space. A simpler linear scan solution runs in O(n) time and O(1) space because it checks elements sequentially until the peak condition is found.