Peak Element Index — Problem Statement & Solution Guide

ArraysMediumModified binary search

TimeO(log n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Peak Element Index problem optimally.

TopicArrays

PatternModified binary search

TimeO(log n)

SpaceO(1)

Problem Description

Given an integer array data, locate the index of a peak element. An element data[i] is a peak if it is strictly greater than its immediate neighbours data[i-1] and data[i+1]. Elements outside the array are treated as negative infinity, so the first or last element can be a peak if it exceeds its sole neighbour. Adjacent values are guaranteed to be distinct, ensuring local comparisons are unambiguous. Return the smallest index among all possible peaks. The required solution must run in O(log n) time by applying a modified binary search.

DSA Pattern Breakdown

"Peak Element Index"

medium

WHY DOES IT MATTER?

Peak finding exemplifies the power of binary search on unimodal or partially ordered data, a pattern that recurs in optimization, load‑balancing, and resource allocation problems where a local optimum suffices.

OPTIMIZATION CHALLENGE

The key insight is that a higher neighbour guarantees the existence of a peak on that side, allowing you to discard half the search space each iteration, reducing time from linear to logarithmic.

REAL-WORLD CONNECTION

In distributed systems, locating a server with maximum load among neighbors mirrors peak detection; by probing load gradients you can quickly converge to a hotspot without scanning every node.

During the interview, compute the mid index, compare it with its immediate neighbours, and move left or right based on which neighbour is larger—no need to track visited indices or extra arrays.

COMPLEXITY AT A GLANCE

⏱ Time:O(log n)

💾 Space:O(1)

Core Theory — Why This Approach?

The peak‑finding problem is a classic example of exploiting monotonicity in an otherwise unsorted array. A naïve scan checks every element and its neighbours, yielding O(n) time, which is acceptable for small inputs but becomes a bottleneck when n reaches millions or when the function is called repeatedly in a larger system. The optimal solution leverages binary search: because adjacent values are distinct, the slope direction tells us which half of the array must contain a peak, guaranteeing a logarithmic reduction each step. This divide‑and‑conquer approach transforms the problem from linear to O(log n) while using only O(1) extra space, illustrating how a simple observation about local ordering can unlock exponential speed‑ups.

Interview Questions on This Problem

Q1How would you modify the binary‑search solution if the array could contain equal adjacent values?

If equal neighbours are allowed, the strict > comparison no longer guarantees a single direction; you must treat a flat region as a potential peak and continue searching both sides or first shrink the flat region to its boundaries before applying the slope‑based binary search.

Q2Explain why the first or last element can be a peak and how your algorithm handles these edge cases without extra checks.

The problem defines out‑of‑bounds neighbours as -∞, so the first element is a peak if it exceeds data[1] and the last if it exceeds data[n‑2]. In the binary‑search implementation, when mid is 0 or n‑1 we simply compare with the existing neighbour; the slope logic naturally returns that index as a peak.

Q3A company asks you to find any peak in a massive distributed array where each node holds a segment. What strategy would you propose?

Perform a local peak search on each node, then exchange the boundary values with neighboring nodes; if a node’s local peak is also greater than the adjacent boundary values, it is a global peak. Otherwise, propagate the larger boundary value directionally, mimicking the binary‑search slope decision across nodes.

Examples

Example 1

Input

[1,3,2,4,1]

Output

Explanation: data[1]=3 is larger than data[0]=1 and data[2]=2, so index 1 is a peak. No earlier index satisfies the peak condition, thus the answer is 1.

Example 2

Input

[5,1,2,3,4]

Output

Explanation: The first element 5 is greater than its only neighbour 1, and the virtual element to its left is -∞. Hence index 0 is a peak and also the smallest possible index.

Example 3

Input

[1,2,3,4,5]

Output

Explanation: Each element is larger than the one before it, so the last element 5 exceeds its left neighbour 4 and the virtual right neighbour -∞. Therefore index 4 is the only peak.

Constraints

1 <= data.length <= 100000
-10^9 <= data[i] <= 10^9
data[i] != data[i+1] for all valid i

Optimal Approach & Strategy

Apply binary search: at each step compare the middle element with its right neighbour; if mid < right, move right, else move left, guaranteeing a peak in O(log n).

Brute Force Approach

Scan the array from left to right, checking each element against its neighbours; return the first index that satisfies the peak condition.

Code Solutions

Language:

JavaScript Solution

Time: O(log n)

function findPeakElement(data){
    let lo=0,hi=data.length-1;
    while(lo<hi){
        const mid=Math.floor((lo+hi)/2);
        if(data[mid]>data[mid+1]) hi=mid; else lo=mid+1;
    }
    return lo;
}
const fs=require('fs');
const input=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length){
    const n=input[0];
    const data=input.slice(1,1+n);
    console.log(findPeakElement(data));
}

#include <bits/stdc++.h>
using namespace std;
int findPeakElement(const vector<int>& data){
    int lo=0,hi=data.size()-1;
    while(lo<hi){
        int mid=lo+(hi-lo)/2;
        if(data[mid]>data[mid+1]) hi=mid; else lo=mid+1;
    }
    return lo;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> data(n);
    for(int i=0;i<n;++i) cin>>data[i];
    cout<<findPeakElement(data);
    return 0;
}

import java.io.*;
import java.util.*;
public class Main{
    public static int findPeakElement(int[] data){
        int lo=0,hi=data.length-1;
        while(lo<hi){
            int mid=lo+(hi-lo)/2;
            if(data[mid]>data[mid+1]) hi=mid; else lo=mid+1;
        }
        return lo;
    }
    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[] data=new int[n];
        int idx=0;
        while(idx<n){
            if(!st.hasMoreTokens()){
                line=br.readLine();
                if(line==null) break;
                st=new StringTokenizer(line);
                continue;
            }
            data[idx++]=Integer.parseInt(st.nextToken());
        }
        System.out.print(findPeakElement(data));
    }
}

def find_peak_element(data):
    lo,hi=0,len(data)-1
    while lo<hi:
        mid=(lo+hi)//2
        if data[mid]>data[mid+1]:
            hi=mid
        else:
            lo=mid+1
    return lo

if __name__=="__main__":
    import sys
    tokens=list(map(int,sys.stdin.read().strip().split()))
    if not tokens:
        sys.exit()
    n=tokens[0]
    arr=tokens[1:1+n]
    print(find_peak_element(arr))

function findPeakElement(data){
    let lo=0,hi=data.length-1;
    while(lo<hi){
        const mid=Math.floor((lo+hi)/2);
        if(data[mid]>data[mid+1]) hi=mid; else lo=mid+1;
    }
    return lo;
}
const fs=require('fs');
const input=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length){
    const n=input[0];
    const data=input.slice(1,1+n);
    console.log(findPeakElement(data));
}

Asked in Top Tech Interviews

Atlassian

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.