Peak Element Index — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Apply binary search: compute mid, if heights[mid] < heights[mid+1] move left pointer to mid+1, else move right pointer to mid; when left equals right, that index is a peak.
O(log n)O(1)Problem Description
Given an integer array heights, find any index i such that heights[i] is greater than or equal to its adjacent elements. For i>0 compare with heights[i-1]; for i< n-1 compare with heights[i+1]. If i is at the left border only the right neighbour is considered, and if i is at the right border only the left neighbour is considered. Return one valid index; if several exist any may be returned. The algorithm must run in O(log n) time and O(1) extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Peak Element Index"
WHY DOES IT MATTER?
Peak‑finding teaches binary‑search on unordered data, a subtle but powerful technique that appears in load‑balancing, resource allocation, and signal‑processing tasks where a local optimum guarantees a global solution.
OPTIMIZATION CHALLENGE
The key insight is the directional monotonicity: if the middle element is lower than its right neighbour, a peak must exist on the right side, allowing us to discard the left half each iteration.
REAL-WORLD CONNECTION
Think of a mountain range represented by sensor heights; locating a summit without scanning every point mirrors how distributed monitoring systems locate a hotspot by probing only a subset of nodes.
During the interview, write the binary‑search loop first, then add the >= checks for boundaries; this prevents off‑by‑one errors and shows you understand edge handling before optimizing.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
The problem asks for any index i where heights[i] is not smaller than its immediate neighbours. This is a classic "peak" definition, but the relaxed >= condition means flat plateaus are also valid peaks. A naive scan checks each element against its neighbours, which is O(n) time and O(1) space, but the interview expects a logarithmic solution that demonstrates binary‑search thinking. By exploiting the monotonic property that if heights[mid] < heights[mid+1] then a peak must exist to the right, we can discard half of the search space each step, yielding O(log n) time while still using O(1) extra space. The optimal paradigm is a divide‑and‑conquer binary search on an unsorted array, a pattern that appears in many “find‑something‑in‑array” problems where a local condition guarantees global existence.
Interview Questions on This Problem
Q1How would you modify the binary‑search solution if the array could contain duplicate values and you must return the leftmost peak?
When heights[mid] == heights[mid+1], move the right pointer leftwards (right = mid) to continue searching the left side; this ensures the algorithm converges to the first index that satisfies the peak condition.
Q2Explain why a peak is guaranteed to exist in any non‑empty integer array under the >= definition.
At the boundaries, the single neighbour comparison ensures the first or last element is a peak if the array is monotonic. If the array rises then falls, the transition point where heights[i] >= heights[i+1] after a rise creates a peak. Hence at least one index always satisfies the condition.
Q3In a distributed system where each node holds a segment of the heights array, how could you find a global peak with minimal communication?
Each node locally finds a candidate peak in its segment using binary search. Nodes then exchange the border values of adjacent segments; if a local candidate fails the border comparison, the neighboring node’s candidate is considered. Only O(log n) messages are needed to converge on a valid global peak.
Examples
Input
[1,3,2,4,1]
Output
1
Explanation: Element at index1 is 3. It is >= left neighbour 1 and >= right neighbour 2, so it satisfies the peak condition. The algorithm can stop here and return 1.
Input
[5,4,3,2,1]
Output
0
Explanation: The first element 5 has only a right neighbour 4. Since 5>=4, index0 is a peak. No need to examine other positions.
Input
[1,2,3,4,5]
Output
4
Explanation: The last element 5 has only a left neighbour 4. Because 5>=4, index4 is a peak. The algorithm can locate this by binary search moving towards the larger side.
Constraints
- 1<=heights.length<=10^5
- -10^9<=heights[i]<=10^9
- All comparisons are integer based
- Expected time complexity O(log n)
Optimal Approach & Strategy
Apply binary search: compute mid, if heights[mid] < heights[mid+1] move left pointer to mid+1, else move right pointer to mid; when left equals right, that index is a peak.
Brute Force Approach
Iterate through the array, compare each element with its left and right neighbours (if they exist), and return the first index that satisfies the condition.
Code Solutions
function findPeakElement(heights){
const n = heights.length;
if(n===0) return -1;
for(let i=0;i<n;i++){
const leftOk = (i===0) || (heights[i] >= heights[i-1]);
const rightOk = (i===n-1) || (heights[i] >= heights[i+1]);
if(leftOk && rightOk) return i;
}
return -1;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n = data[0];
const heights = data.slice(1,1+n);
const ans = findPeakElement(heights);
process.stdout.write(String(ans));
}
main();#include <bits/stdc++.h>
using namespace std;
int findPeakElement(const vector<int>& heights) {
int n = heights.size();
if(n==0) return -1;
for(int i=0;i<n;++i){
bool leftOk = (i==0) || (heights[i] >= heights[i-1]);
bool rightOk = (i==n-1) || (heights[i] >= heights[i+1]);
if(leftOk && rightOk) return i;
}
return -1; // should never reach
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> a(n); for(int i=0;i<n;++i)cin>>a[i];
cout<<findPeakElement(a);
return 0;}
import java.io.*;
import java.util.*;
public class Main {
public static int findPeakElement(int[] heights) {
int n = heights.length;
if(n==0) return -1;
for(int i=0;i<n;i++){
boolean leftOk = (i==0) || (heights[i] >= heights[i-1]);
boolean rightOk = (i==n-1) || (heights[i] >= heights[i+1]);
if(leftOk && rightOk) return i;
}
return -1;
}
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;
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
int[] heights = new int[n];
int idx = 0;
while(idx < n) {
if(!st.hasMoreTokens()) {
line = br.readLine();
if(line==null) break;
st = new StringTokenizer(line);
continue;
}
heights[idx++] = Integer.parseInt(st.nextToken());
}
System.out.print(findPeakElement(heights));
}
}
def find_peak_element(heights):
n = len(heights)
if n == 0:
return -1
for i in range(n):
left_ok = (i == 0) or (heights[i] >= heights[i-1])
right_ok = (i == n-1) or (heights[i] >= heights[i+1])
if left_ok and right_ok:
return i
return -1
def main():
import sys
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
heights = list(map(int, data[1:1+n]))
print(find_peak_element(heights))
if __name__ == "__main__":
main()
function findPeakElement(heights){
const n = heights.length;
if(n===0) return -1;
for(let i=0;i<n;i++){
const leftOk = (i===0) || (heights[i] >= heights[i-1]);
const rightOk = (i===n-1) || (heights[i] >= heights[i+1]);
if(leftOk && rightOk) return i;
}
return -1;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n = data[0];
const heights = data.slice(1,1+n);
const ans = findPeakElement(heights);
process.stdout.write(String(ans));
}
main();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.