Peak Temperature Indices — Problem Statement & Solution Guide

ArraysMediumArray traversal and pattern recognition

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

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

TopicArrays

PatternArray traversal and pattern recognition

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array thermalReadings, identify every position i that has both a left and a right neighbor and whose value is strictly larger than the values at i-1 and i+1. Return all such indices in ascending order. If the array length is less than three, the result is an empty list.

DSA Pattern Breakdown

"Peak Temperature Indices"

medium

WHY DOES IT MATTER?

Detecting local maxima is a fundamental pattern in signal processing, anomaly detection, and performance monitoring, where identifying spikes quickly can trigger alerts or optimizations.

OPTIMIZATION CHALLENGE

The insight is that the peak condition is *local*—it never requires information beyond immediate neighbors—so a single forward pass suffices, eliminating any need for nested loops or extra data structures.

REAL-WORLD CONNECTION

Think of a network of temperature sensors along a pipeline; peaks indicate potential overheating zones that need immediate attention, mirroring the algorithm's role in flagging critical points.

During the interview, write the loop bounds clearly (i=1; i<len-1) and immediately return the collected indices; this avoids off‑by‑one bugs and shows you respect edge constraints.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

Local peaks (or "mountain tops") in an array are positions whose value exceeds both immediate neighbors. The naïve way is to compare each element with every other element or to recompute neighbor relationships repeatedly, which can balloon to O(n²) time on large inputs. The optimal paradigm leverages the fact that the condition only depends on the two adjacent values, allowing a single linear scan: for each index i from 1 to n‑2 we simply check thermalReadings[i]>thermalReadings[i-1] && thermalReadings[i]>thermalReadings[i+1]. This yields O(n) time and O(1) auxiliary space, which scales gracefully even for millions of readings. Moreover, because we only need indices, we can emit results on‑the‑fly, preserving order without extra sorting, making the solution both time‑ and memory‑efficient.

Interview Questions on This Problem

Q1How would you adapt the algorithm to return the peak values themselves instead of their indices?

During the linear scan, push thermalReadings[i] into the result list whenever the peak condition holds; the rest of the logic remains unchanged.

Q2If the array were circular (the first and last elements are neighbors), how does the solution change?

You must treat index 0 and n‑1 as having each other as a neighbor, so you check those two positions separately while still scanning the interior indices in O(n) time.

Q3Can you compute the number of peaks without storing any indices?

Yes, maintain a counter that increments each time the peak condition is satisfied during the single pass; this uses O(1) extra space.

Examples

Example 1

Input

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

Output

[2,5]

Explanation: Index 2 holds 5, which is greater than its neighbors 2 and 1. Index 5 holds 7, greater than its neighbors 3 and 6. No other index satisfies the condition, so the result is [2,5].

Example 2

Input

[10,9,8,7]

Output

[]

Explanation: Every element is either at the boundary or not larger than both neighbours; therefore no peak indices exist.

Example 3

Input

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

Output

[1,3,5]

Explanation: Index 1 (3) > 1 and 2, index 3 (4) > 2 and 3, index 5 (5) > 3 and 4; these are the only peaks.

Constraints

1 <= thermalReadings.length <= 100000
-1000000000 <= thermalReadings[i] <= 1000000000
Solution must run in O(n) time and O(1) extra space.

Optimal Approach & Strategy

Traverse the array once, checking only the two adjacent values for each interior index, achieving O(n) time and O(1) extra space.

Brute Force Approach

For each index, compare it with every other element to verify it’s larger than both neighbors, leading to O(n²) 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 pos = 0;
const n = data[pos++] || 0;
const arr = data.slice(pos, pos + n);
function peakIndices(thermalReadings){
    const res = [];
    for(let i=1;i+1<thermalReadings.length;i++){
        if(thermalReadings[i] > thermalReadings[i-1] && thermalReadings[i] > thermalReadings[i+1])
            res.push(i);
    }
    return res;
}
const result = peakIndices(arr);
console.log(result.join(' '));

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

vector<int> peakIndices(const vector<int>& thermalReadings) {
    vector<int> ans;
    int n = thermalReadings.size();
    for(int i=1;i+1<n;++i){
        if(thermalReadings[i] > thermalReadings[i-1] && thermalReadings[i] > thermalReadings[i+1])
            ans.push_back(i);
    }
    return ans;
}

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

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

public class Main {
    public static List<Integer> peakIndices(int[] thermalReadings) {
        List<Integer> ans = new ArrayList<>();
        for(int i=1;i+1<thermalReadings.length;i++){
            if(thermalReadings[i] > thermalReadings[i-1] && thermalReadings[i] > thermalReadings[i+1])
                ans.add(i);
        }
        return ans;
    }

    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());
        }
        List<Integer> res = peakIndices(arr);
        for(int i=0;i<res.size();i++){
            if(i>0) System.out.print(" ");
            System.out.print(res.get(i));
        }
        System.out.println();
    }
}

import sys

def peak_indices(thermalReadings):
    res = []
    for i in range(1, len(thermalReadings)-1):
        if thermalReadings[i] > thermalReadings[i-1] and thermalReadings[i] > thermalReadings[i+1]:
            res.append(i)
    return res

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    arr = list(map(int, data[1:1+n]))
    res = peak_indices(arr)
    print(' '.join(map(str, res)))

if __name__ == "__main__":
    main()

const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++] || 0;
const arr = data.slice(pos, pos + n);
function peakIndices(thermalReadings){
    const res = [];
    for(let i=1;i+1<thermalReadings.length;i++){
        if(thermalReadings[i] > thermalReadings[i-1] && thermalReadings[i] > thermalReadings[i+1])
            res.push(i);
    }
    return res;
}
const result = peakIndices(arr);
console.log(result.join(' '));

Asked in Top Tech Interviews

PhonePeZomato

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.