Peak Index in Array — Problem Statement & Solution Guide

ArraysMediumFinding the maximum/minimum index with specific conditions

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

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

TopicArrays

PatternFinding the maximum/minimum index with specific conditions

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array yields, identify the smallest index i (0‑based) such that i is not the first or last position and yields[i] is strictly greater than both yields[i‑1] and yields[i+1]. If no index satisfies this condition, return -1. The algorithm must run in linear time and use constant extra space.

DSA Pattern Breakdown

"Peak Index in Array"

medium

WHY DOES IT MATTER?

Detecting local maxima (or minima) is a fundamental pattern in algorithmic problem solving; it appears in signal processing, stock‑price analysis, and even in designing efficient search heuristics. Mastering this pattern teaches you to reason about neighbourhood relationships without extra data structures.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that you do not need to store or recompute any prefix/suffix information; a single forward pass with constant‑size variables can decide the answer as soon as the first qualifying element appears.

REAL-WORLD CONNECTION

Think of a distributed monitoring system that raises an alert when a metric spikes higher than its immediate past and future readings – the alert logic mirrors the peak‑index check, needing only the current and two adjacent samples.

During an interview, state the problem, outline the O(n) scan, and immediately mention the early‑exit condition. This shows you respect both time and space constraints and that you can translate the mathematical definition into clean code.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the first "peak" element in an array – an index i (not at the boundaries) where yields[i] > yields[i-1] and yields[i] > yields[i+1]. A naive solution would examine every interior element and compare it with its two neighbours, which is already O(n) time but still scans the whole array even after a valid peak is found. The real inefficiency appears when candidates try to use nested loops, binary search without monotonicity, or extra data structures, inflating the runtime to O(n log n) or O(n^2) and breaking the constant‑space requirement. The optimal paradigm leverages the fact that we only need the *first* qualifying peak, so a single linear scan suffices: iterate from i = 1 to n‑2, and as soon as yields[i] > yields[i-1] && yields[i] > yields[i+1] return i. This approach respects the O(n) time bound and O(1) auxiliary space, making it ideal for large inputs where memory and latency are critical.

Interview Questions on This Problem

Q1At a global product company you are asked to return the smallest peak index in an integer array, or -1 if none exists. How would you implement it in O(n) time and O(1) space?

Iterate i from 1 to len-2; if arr[i] > arr[i-1] && arr[i] > arr[i+1] return i immediately. After the loop, return -1. This single pass uses only a few integer variables.

Q2A fintech platform wants to detect a local maximum price in a time‑series where the first and last timestamps cannot be peaks. How would you adapt the peak‑index solution to also return all peak positions?

Use the same linear scan but instead of returning on the first match, push every i that satisfies arr[i] > arr[i-1] && arr[i] > arr[i+1] into a result list. The scan remains O(n) and uses O(k) extra space where k is the number of peaks.

Q3A high‑growth startup asks you to find a peak in a circular array where the first and last elements are neighbours. What change is required in the algorithm?

Treat the array as circular by checking the first element against arr[n-1] and arr[1], and the last element against arr[n-2] and arr[0]. Then perform a linear scan on the interior indices as before, returning the first index that satisfies the circular neighbour condition.

Examples

Example 1

Input

[1,3,2,4,1]

Output

Explanation: Index 1 holds value 3. Its left neighbor is 1 and right neighbor is 2; 3>1 and 3>2, so index 1 is the first peak.

Example 2

Input

[5,4,3,2,1]

Output

-1

Explanation: Every element is non‑increasing, therefore no interior element is larger than both neighbours; the function returns -1.

Example 3

Input

[2,1,2,3,4,5,4,3]

Output

Explanation: Scanning from the left, indices 2 and 3 are not peaks because their right neighbour is larger. At index 5 the value is 5, left neighbour 4 and right neighbour 4; 5>4 and 5>4, making it the first valid peak.

Constraints

1 <= yields.length <= 100000
-1000000000 <= yields[i] <= 1000000000
Time complexity O(n)
Auxiliary space O(1)

Optimal Approach & Strategy

Perform a single linear pass from index 1 to n‑2, returning immediately when a peak is detected. The algorithm uses only a few integer variables, achieving O(n) time and O(1) extra space.

Brute Force Approach

Check every interior element against its two neighbours, recording the first index that satisfies the condition, then return -1 if none do. This still scans the whole array even after a valid peak is found, wasting time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0; const n=data[p++]||0; const yields=data.slice(p,p+n);
function peakIndex(yields){
    for(let i=1;i<yields.length-1;i++){
        if(yields[i]>yields[i-1] && yields[i]>yields[i+1]) return i;
    }
    return -1;
}
console.log(peakIndex(yields).toString());

#include <bits/stdc++.h>
using namespace std;
int peakIndex(const vector<int>& yields){
    int n=yields.size();
    for(int i=1;i+1<n;++i){
        if(yields[i]>yields[i-1] && yields[i]>yields[i+1]) return i;
    }
    return -1;
}
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 {
    static int peakIndex(int[] yields){
        for(int i=1;i<yields.length-1;i++){
            if(yields[i]>yields[i-1] && yields[i]>yields[i+1]) 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;
        int n = Integer.parseInt(line.trim());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) arr[i]=Integer.parseInt(st.nextToken());
        System.out.print(peakIndex(arr));
    }
}

import sys
def peak_index(yields):
    for i in range(1, len(yields)-1):
        if yields[i] > yields[i-1] and yields[i] > yields[i+1]:
            return i
    return -1
def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    yields = list(map(int, data[1:1+n]))
    print(peak_index(yields))
if __name__ == "__main__":
    main()

const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0; const n=data[p++]||0; const yields=data.slice(p,p+n);
function peakIndex(yields){
    for(let i=1;i<yields.length-1;i++){
        if(yields[i]>yields[i-1] && yields[i]>yields[i+1]) return i;
    }
    return -1;
}
console.log(peakIndex(yields).toString());

Asked in Top Tech Interviews

AmazonAtlassian

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.