Temperature Sensor Analysis — Problem Statement & Solution Guide
Problem Description
Given an integer array nums representing sequential temperature readings, return all positions i such that nums[i] is greater than or equal to its immediate neighbor(s). For interior indices both left and right neighbours must be considered; for the first index only the right neighbour and for the last index only the left neighbour are relevant. The result must be a list of zero‑based indices sorted in ascending order. If no index satisfies the condition, return an empty list.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Temperature Sensor Analysis"
WHY DOES IT MATTER?
Identifying local extrema with minimal overhead is a core skill for performance‑critical code, especially in sensor data pipelines where latency and memory footprints are tightly constrained.
OPTIMIZATION CHALLENGE
The key insight is that each element’s eligibility depends solely on at most two neighbours, allowing constant‑time checks per element and eliminating the need for sorting, heaps, or additional passes.
REAL-WORLD CONNECTION
Think of a distributed monitoring system where each node reports a metric; you only need to flag a node if its metric isn’t lower than its immediate peers, mirroring the neighbor‑comparison logic used in load‑balancing decisions.
During an interview, write the loop that handles the three cases (first, interior, last) explicitly; this avoids off‑by‑one errors and demonstrates clear boundary handling.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for indices where a temperature reading is not lower than its immediate neighbor(s). A naïve solution would compare each element with its neighbours in O(n) time, which is already optimal for a single pass, but many candidates mistakenly think they need extra data structures or multiple passes, inflating both time and space. The optimal paradigm leverages the fact that each element’s relationship to its neighbours can be decided in constant time, allowing a single linear scan while building the result list on‑the‑fly. This approach exemplifies the “single‑pass array scan” pattern, where local comparisons drive global results without auxiliary storage beyond the output, guaranteeing O(n) time and O(1) auxiliary space.
Interview Questions on This Problem
Q1How would you modify the solution if the requirement changed to find indices where nums[i] is strictly greater than both neighbours?
Change the comparison operators to '>' for interior indices while keeping the edge cases (first and last) to compare only with the single neighbour using '>' as well; the rest of the linear scan remains unchanged.
Q2Can this problem be solved using a divide‑and‑conquer approach, and would it be beneficial?
While a divide‑and‑conquer could recursively process sub‑arrays, each merge step would still need to examine the boundary elements, resulting in O(n log n) time and extra space, which is inferior to the straightforward O(n) scan; thus it is not beneficial.
Q3In a streaming context where temperatures arrive one‑by‑one, how would you emit qualifying indices in real time?
Maintain the previous value and its index; when a new value arrives, compare it with the previous to decide if the previous index qualifies, and also compare the new value with the previous to potentially qualify the new index later, achieving O(1) per element with constant memory.
Examples
Input
[4,4,2,5,3]
Output
[0,1,3]
Explanation: Index 0: 4 >= right neighbour 4. Index 1: 4 >= left 4 and >= right 2. Index 2 fails because 2 < left 4. Index 3: 5 >= left 2 and >= right 3. Index 4 fails because 3 < left 5.
Input
[7]
Output
[0]
Explanation: Single element has no neighbours, so it trivially satisfies the condition.
Input
[-1,-3,-2,-2,-5]
Output
[0,2,3]
Explanation: Index0:-1 >= right -3. Index1 fails (-3 < left -1). Index2:-2 >= left -3 and >= right -2. Index3:-2 >= left -2 and >= right -5. Index4 fails because -5 < left -2.
Constraints
- 1 <= nums.length <= 100000
- -10^9 <= nums[i] <= 10^9
- All operations must run in O(n) time and O(1) extra space beyond the output list
Optimal Approach & Strategy
Perform a single pass, comparing each element only with its immediate neighbour(s) and collecting qualifying indices, achieving O(n) time.
Brute Force Approach
Iterate over every index and, for each, compare with all other elements to determine if it’s a local maximum, resulting in O(n^2) time.
Verified Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++]||0;
const nums = data.slice(pos, pos+n);
function temperatureSensorAnalysis(nums){
const res=[];
for(let i=0;i<nums.length;i++){
let ok=true;
if(i>0 && nums[i] < nums[i-1]) ok=false;
if(i+1<nums.length && nums[i] < nums[i+1]) ok=false;
if(ok) res.push(i);
}
return res;
}
const result = temperatureSensorAnalysis(nums);
console.log(result.join(' '));#include <bits/stdc++.h>
using namespace std;
vector<int> temperatureSensorAnalysis(const vector<int>& nums) {
vector<int> ans;
int n = nums.size();
for(int i=0;i<n;++i){
bool ok = true;
if(i>0 && nums[i] < nums[i-1]) ok = false;
if(i+1<n && nums[i] < nums[i+1]) ok = false;
if(ok) 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> nums(n);
for(int i=0;i<n;++i) cin>>nums[i];
vector<int> res = temperatureSensorAnalysis(nums);
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> temperatureSensorAnalysis(int[] nums) {
List<Integer> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
boolean ok = true;
if (i > 0 && nums[i] < nums[i - 1]) ok = false;
if (i + 1 < n && nums[i] < nums[i + 1]) ok = false;
if (ok) 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[] nums = new int[n];
if (n > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
}
List<Integer> res = temperatureSensorAnalysis(nums);
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 temperatureSensorAnalysis(nums):
res=[]
n=len(nums)
for i in range(n):
ok=True
if i>0 and nums[i] < nums[i-1]:
ok=False
if i+1<n and nums[i] < nums[i+1]:
ok=False
if ok:
res.append(i)
return res
def main():
data=sys.stdin.read().strip().split()
if not data:
return
n=int(data[0])
nums=list(map(int,data[1:1+n]))
res=temperatureSensorAnalysis(nums)
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 nums = data.slice(pos, pos+n);
function temperatureSensorAnalysis(nums){
const res=[];
for(let i=0;i<nums.length;i++){
let ok=true;
if(i>0 && nums[i] < nums[i-1]) ok=false;
if(i+1<nums.length && nums[i] < nums[i+1]) ok=false;
if(ok) res.push(i);
}
return res;
}
const result = temperatureSensorAnalysis(nums);
console.log(result.join(' '));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.