Peak Index Locator — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Peak Index Locator problem optimally.
O(log n)O(1)Problem Description
You are given a strictly unimodal array mountainSequence of distinct integers. The sequence exhibits a single local maximum: all elements strictly increase up to this peak, and strictly decrease thereafter. The first and last elements are guaranteed to be strictly smaller than their immediate neighbors, ensuring the peak is not at the boundary.
Your task is to determine and return the zero-based index of the peak element. Since the array is strictly unimodal, there is exactly one peak. You must achieve this in O(log n) time complexity by leveraging the structural properties of the sequence, rather than performing a linear scan.
Input: An array mountainSequence of length n, where n >= 3.
Output: An integer representing the index of the maximum element in mountainSequence.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Peak Index Locator"
WHY DOES IT MATTER?
Binary search on a monotonic slope is a classic example of exploiting problem‑specific order to achieve logarithmic time, a pattern that recurs in search, optimization, and decision‑making problems.
OPTIMIZATION CHALLENGE
The key insight is that comparing an element with its right neighbour tells you which half of the array cannot contain the peak, allowing you to discard it each iteration.
REAL-WORLD CONNECTION
Think of a mountain‑range telemetry system that reports altitude as a sensor moves up a ridge and then down; locating the highest point quickly is analogous to routing a packet to the node with maximum load before it starts decreasing.
During the interview, write the binary‑search loop first, then add the mid‑right comparison; avoid off‑by‑one errors by using a half‑open interval [low,high) or inclusive bounds with careful mid calculation.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
In a strictly unimodal (mountain) array the values increase monotonically up to a single peak and then decrease monotonically. A naïve linear scan that checks each element’s neighbours finds the peak in O(n) time, which is acceptable for small inputs but becomes a bottleneck when n reaches 10⁶ or higher, especially under tight time‑limits typical of coding interviews. The optimal solution leverages the monotonic property on both sides of the peak and applies binary search: by comparing the middle element with its right neighbour we can decide whether we are on the ascending slope (move right) or descending slope (move left). This halves the search space each iteration, yielding O(log n) time while using O(1) extra space.
Interview Questions on This Problem
Q1How would you modify the algorithm to return the peak index if the array could contain multiple equal‑height peaks?
Use a variant of binary search that, when mid equals its neighbours, expands outward to locate the leftmost or rightmost plateau, or fall back to a linear scan of the plateau; the overall complexity remains O(log n) for the search plus O(k) for plateau size k.
Q2Can you solve the peak index problem in a single pass without extra space while guaranteeing O(n) worst‑case time?
Yes, a simple linear scan that tracks the maximum value and its index does the job in O(n) time and O(1) space, but it does not improve over the naïve approach; the interview expects you to discuss why binary search is preferable for large n.
Q3How would you adapt the solution for a streamed input where you cannot store the entire array in memory?
Maintain a sliding window of three elements; when the middle element is greater than both neighbours you have found the peak, otherwise continue streaming. This works because the peak is guaranteed to exist and be unique, giving O(1) memory and O(n) time.
Examples
Input
mountainSequence = [3, 8, 12, 15, 9, 4, 1]
Output
3
Explanation: The array increases from index 0 to 3 (3 < 8 < 12 < 15) and decreases from index 3 to 6 (15 > 9 > 4 > 1). The peak value is 15, located at index 3. Binary search compares mid elements with their neighbors to narrow the search space: mid=3, arr[3]=15, arr[2]=12, arr[4]=9. Since arr[3] > arr[2] and arr[3] > arr[4], index 3 is the peak.
Input
mountainSequence = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Output
9
Explanation: The sequence strictly increases from index 0 to 9 (1 to 10) and strictly decreases from index 9 to 18 (10 to 1). The peak value 10 is at index 9. Binary search: low=0, high=18, mid=9. arr[9]=10, arr[8]=9, arr[10]=9. Since arr[9] > arr[8] and arr[9] > arr[10], index 9 is returned.
Input
mountainSequence = [50, 60, 70, 80, 90, 85, 75, 65, 55, 45]
Output
4
Explanation: Values increase from 50 to 90 (indices 0-4) and decrease from 90 to 45 (indices 4-9). The peak is 90 at index 4. Binary search: low=0, high=9, mid=4. arr[4]=90, arr[3]=80, arr[5]=85. Since arr[4] > arr[3] and arr[4] > arr[5], index 4 is the peak.
Input
mountainSequence = [10, 20, 30, 25, 15, 5]
Output
2
Explanation: The array increases from 10 to 30 (indices 0-2) and decreases from 30 to 5 (indices 2-5). The peak value 30 is at index 2. Binary search: low=0, high=5, mid=2. arr[2]=30, arr[1]=20, arr[3]=25. Since arr[2] > arr[1] and arr[2] > arr[3], index 2 is returned.
Constraints
- 3 <= mountainSequence.length <= 10^5
- 1 <= mountainSequence[i] <= 10^9
- All elements in mountainSequence are distinct
- mountainSequence[0] < mountainSequence[1]
- mountainSequence[mountainSequence.length - 1] < mountainSequence[mountainSequence.length - 2]
Optimal Approach & Strategy
Use binary search on the slope: compare mid with mid+1 and move left or right accordingly; this runs in O(log n) time.
Brute Force Approach
Scan each element and return the index where it is greater than both neighbours; this is O(n) time.
Code Solutions
function peakIndex(mountainSequence){
let l=0, r=mountainSequence.length-1;
while(l<r){
const mid = Math.floor(l + (r-l)/2);
if(mountainSequence[mid] < mountainSequence[mid+1]) l = mid+1;
else r = mid;
}
return l;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length){
const n = data[0];
const arr = data.slice(1,1+n);
console.log(peakIndex(arr));
}#include <bits/stdc++.h>
using namespace std;
int peakIndex(const vector<int>& a){
int l=0, r=(int)a.size()-1;
while(l<r){
int mid = l + (r-l)/2;
if(a[mid] < a[mid+1]) l = mid+1;
else r = mid;
}
return l;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> arr(n);
for(int i=0;i<n;++i) cin>>arr[i];
cout<<peakIndex(arr);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int peakIndex(int[] a){
int l=0, r=a.length-1;
while(l<r){
int mid = l + (r-l)/2;
if(a[mid] < a[mid+1]) l = mid+1;
else r = mid;
}
return l;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
arr[i] = Integer.parseInt(st.nextToken());
}
System.out.print(peakIndex(arr));
}
}import sys
def peak_index(mountain_sequence):
l, r = 0, len(mountain_sequence)-1
while l < r:
mid = (l + r)//2
if mountain_sequence[mid] < mountain_sequence[mid+1]:
l = mid + 1
else:
r = mid
return l
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
arr = list(map(int, data[1:1+n]))
print(peak_index(arr))
if __name__ == "__main__":
main()function peakIndex(mountainSequence){
let l=0, r=mountainSequence.length-1;
while(l<r){
const mid = Math.floor(l + (r-l)/2);
if(mountainSequence[mid] < mountainSequence[mid+1]) l = mid+1;
else r = mid;
}
return l;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length){
const n = data[0];
const arr = data.slice(1,1+n);
console.log(peakIndex(arr));
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.