Peak Energy Indices — Problem Statement & Solution Guide

ArraysMediumSliding Window

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Peak Energy Indices problem optimally.

TopicArrays

PatternSliding Window

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array energyReadings, return all indices i such that energyReadings[i] is not smaller than each of its immediate neighbours. For a middle element (0<i< n‑1) this means energyReadings[i] ≥ energyReadings[i‑1] and energyReadings[i] ≥ energyReadings[i+1]. For the first element (i=0) only the right neighbour is considered, and for the last element (i=n‑1) only the left neighbour is considered. The result must list the qualifying indices in increasing order. An O(n) scan using a sliding window of size three can determine each peak in constant extra space.

DSA Pattern Breakdown

"Peak Energy Indices"

medium

WHY DOES IT MATTER?

Peak detection appears in signal processing, stock price analysis, and load‑balancing heuristics, making the ability to identify local maxima efficiently a reusable skill across domains.

OPTIMIZATION CHALLENGE

The key insight is that each element’s neighbour information is independent, so you can evaluate the condition in a single linear sweep without nested loops or extra data structures.

REAL-WORLD CONNECTION

Think of a server farm where each node reports its current load; a node is a "peak" if its load is not lower than its immediate neighbours, indicating a potential bottleneck that needs throttling or redistribution.

During an interview, write the loop that checks the boundary cases first (i==0 and i==n‑1) then the generic case; this avoids off‑by‑one bugs and demonstrates clean handling of edge conditions.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem is a classic example of a local‑maximum detection task on a one‑dimensional array. A naive scan that compares each element with its neighbours yields a linear‑time solution, but understanding why this works requires a grasp of the "peak" property: an index i is a peak if its value is not smaller than any of its immediate neighbours. The naive O(n²) approach would re‑compare ranges or recompute neighbour information, which quickly becomes prohibitive for large n because it repeats work already known from adjacent checks. The optimal paradigm leverages the fact that each element’s neighbours are fixed and can be examined exactly once, allowing a single pass with constant auxiliary state. This reduces the algorithm to O(n) time and O(1) extra space, which scales to massive input sizes common in production telemetry streams.

Interview Questions on This Problem

Q1How would you modify the solution to return the values of the peaks instead of their indices, and what edge cases must you handle?

Iterate once, checking the same neighbour conditions, and push energyReadings[i] into the result when the condition holds. Edge cases include arrays of length 1 (the sole element is a peak) and handling equal neighbours correctly, as the definition uses >=.

Q2Can you design a version that finds all peaks in a circular array where the first and last elements are also neighbours?

Treat the array as circular by comparing index 0 with index n‑1 and index n‑1 with index 0. In a single pass, for each i compute left = (i‑1+n)%n and right = (i+1)%n, then check the >= condition. This still runs in O(n) time and O(1) space.

Q3What is the time‑space trade‑off if you pre‑compute a prefix‑max and suffix‑max array to answer multiple peak‑queries on the same data?

Building prefix‑max and suffix‑max arrays takes O(n) time and O(n) space, after which each query for a specific index can be answered in O(1) by comparing the stored maxima, which is beneficial when the number of queries is large compared to the array size.

Examples

Example 1

Input

[5,3,4,4,2]

Output

[0,2,3]

Explanation: Index 0: 5≥3 → peak. Index 1: 3<5 and 3<4 → not a peak. Index 2: 4≥3 and 4≥4 → peak. Index 3: 4≥4 and 4≥2 → peak. Index 4: 2<4 → not a peak. Collected peaks are [0,2,3].

Example 2

Input

[1,2,3,4,5]

Output

[4]

Explanation: Only the last element has a single neighbour to compare with. 5≥4, so index 4 is a peak. All other positions have a right neighbour larger than themselves, thus they fail the condition.

Example 3

Input

[9,9,9]

Output

[0,1,2]

Explanation: Each element is equal to its neighbour(s). Equality satisfies the ≥ condition, so every index (0,1,2) is a peak.

Constraints

1 <= energyReadings.length <= 100000
-1000000000 <= energyReadings[i] <= 1000000000
Expected time complexity: O(n)
Expected auxiliary space: O(1)

Optimal Approach & Strategy

Traverse the array once, compare each element only with its immediate left and right neighbours, handling boundaries separately, achieving O(n) time and O(1) extra space.

Brute Force Approach

Check every index against all other indices or recompute neighbour ranges, leading to O(n²) time because of repeated work.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) process.exit(0);
let pos = 0;
const n = data[pos++];
const energyReadings = data.slice(pos, pos + n);

function peakEnergyIndices(energyReadings) {
    const peaks = [];
    const len = energyReadings.length;
    for (let i = 0; i < len; i++) {
        const leftOk = (i === 0) || (energyReadings[i] >= energyReadings[i - 1]);
        const rightOk = (i === len - 1) || (energyReadings[i] >= energyReadings[i + 1]);
        if (leftOk && rightOk) peaks.push(i);
    }
    return peaks;
}

const result = peakEnergyIndices(energyReadings);
console.log(result.join(' '));

#include <bits/stdc++.h>
using namespace std;

vector<int> peakEnergyIndices(const vector<int>& energyReadings) {
    vector<int> peaks;
    int n = (int)energyReadings.size();
    for (int i = 0; i < n; ++i) {
        bool leftOk = (i == 0) || (energyReadings[i] >= energyReadings[i - 1]);
        bool rightOk = (i == n - 1) || (energyReadings[i] >= energyReadings[i + 1]);
        if (leftOk && rightOk) peaks.push_back(i);
    }
    return peaks;
}

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];
    vector<int> ans = peakEnergyIndices(arr);
    for (size_t i = 0; i < ans.size(); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static List<Integer> peakEnergyIndices(int[] energyReadings) {
        List<Integer> peaks = new ArrayList<>();
        int n = energyReadings.length;
        for (int i = 0; i < n; i++) {
            boolean leftOk = (i == 0) || (energyReadings[i] >= energyReadings[i - 1]);
            boolean rightOk = (i == n - 1) || (energyReadings[i] >= energyReadings[i + 1]);
            if (leftOk && rightOk) {
                peaks.add(i);
            }
        }
        return peaks;
    }

    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());
        }
        List<Integer> res = peakEnergyIndices(arr);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.size(); i++) {
            if (i > 0) sb.append(' ');
            sb.append(res.get(i));
        }
        System.out.println(sb.toString());
    }
}

import sys

def peak_energy_indices(energyReadings):
    peaks = []
    n = len(energyReadings)
    for i in range(n):
        left_ok = (i == 0) or (energyReadings[i] >= energyReadings[i - 1])
        right_ok = (i == n - 1) or (energyReadings[i] >= energyReadings[i + 1])
        if left_ok and right_ok:
            peaks.append(i)
    return peaks

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

const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) process.exit(0);
let pos = 0;
const n = data[pos++];
const energyReadings = data.slice(pos, pos + n);

function peakEnergyIndices(energyReadings) {
    const peaks = [];
    const len = energyReadings.length;
    for (let i = 0; i < len; i++) {
        const leftOk = (i === 0) || (energyReadings[i] >= energyReadings[i - 1]);
        const rightOk = (i === len - 1) || (energyReadings[i] >= energyReadings[i + 1]);
        if (leftOk && rightOk) peaks.push(i);
    }
    return peaks;
}

const result = peakEnergyIndices(energyReadings);
console.log(result.join(' '));

Asked in Top Tech Interviews

Flipkart

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.