Galaxy Anomaly Detector — Problem Statement & Solution Guide
Problem Description
You are tasked with processing a linear sequence of integer values representing signal intensities from a distributed sensor array. The input is provided as an array signals of length n. An index i is classified as a 'peak' if the value at i is strictly greater than its immediate neighbors. For boundary indices, the element at index 0 is a peak if it is strictly greater than signals[1], and the element at index n-1 is a peak if it is strictly greater than signals[n-2]. If the array contains only one element, that element is considered a peak.
Your objective is to identify all indices that satisfy the peak condition. Return an array containing these indices in ascending order. If no peaks exist, return an empty array.
Note that the values in the array are not guaranteed to be distinct, but the peak condition requires strict inequality.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galaxy Anomaly Detector"
WHY DOES IT MATTER?
This pattern is essential for any application involving time-series data, signal processing, or anomaly detection. It teaches candidates how to handle boundary conditions and strict inequality checks, which are common pitfalls in array problems. Understanding this pattern helps in designing efficient algorithms for real-world data streams.
OPTIMIZATION CHALLENGE
The key insight is that you only need to compare each element with its immediate neighbors. This reduces the problem to a single pass through the array, avoiding the need for sorting or complex data structures. The challenge is to correctly handle the boundary indices and ensure that the strict inequality condition is met.
REAL-WORLD CONNECTION
In distributed sensor networks, peak detection is used to identify anomalies in sensor readings, such as temperature spikes or pressure drops. This is critical for predictive maintenance in industrial IoT systems, where early detection of anomalies can prevent costly failures.
During the interview, clearly state your assumptions about boundary conditions and strict inequality. Ask clarifying questions about whether the array is sorted or if there are any constraints on the values. This shows that you are thinking about edge cases and real-world applicability.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem of identifying local maxima in a linear array is a classic application of the 'sliding window' or 'neighbor comparison' pattern. The core theoretical challenge lies in handling boundary conditions and strict inequality definitions. A naive approach might involve checking every element against its neighbors, which is computationally trivial for small arrays but reveals deeper insights when scaled. The fundamental concept here is that a peak is defined by its relationship to immediate neighbors, not global properties. For an array of length n, indices 0 and n-1 have only one neighbor, while internal indices have two. The strict inequality condition (>) ensures that plateaus (equal values) are not considered peaks, which is critical for signal processing applications where noise might create flat regions.
Interview Questions on This Problem
Q1At a fintech platform processing high-frequency trading signals, how would you modify the peak detection logic to handle noisy data where small fluctuations might create false peaks?
You would introduce a threshold or epsilon value. Instead of checking if signals[i] > signals[i-1] and signals[i] > signals[i+1], you would check if signals[i] > signals[i-1] + epsilon and signals[i] > signals[i+1] + epsilon. This filters out minor noise-induced fluctuations, ensuring only significant anomalies are flagged. This is a common requirement in real-world signal processing to reduce false positives.
Q2In a distributed sensor array, if the array is too large to fit in memory, how would you design a streaming algorithm to detect peaks?
You would process the stream in a single pass, maintaining only the previous two values (prev2, prev1) and the current value. As each new value arrives, you can check if prev1 was a peak by comparing it with prev2 and the current value. This requires O(1) space and O(n) time, making it suitable for streaming data where the entire array cannot be loaded into memory.
Q3For a high-growth startup building a real-time anomaly detection system, how would you optimize the peak detection to run in parallel across multiple cores?
You can divide the array into chunks and process each chunk in parallel. However, you must handle the boundaries between chunks carefully. The last element of one chunk and the first element of the next chunk need to be checked together to ensure no peaks are missed at the boundaries. This requires a two-pass approach or a careful merge step to combine results from parallel workers.
Examples
Input
signals = [1, 3, 2, 4, 1]
Output
[1, 3]
Explanation: Index 0: 1 < 3 (not a peak). Index 1: 3 > 1 and 3 > 2 (peak). Index 2: 2 < 3 and 2 < 4 (not a peak). Index 3: 4 > 2 and 4 > 1 (peak). Index 4: 1 < 4 (not a peak). Result: [1, 3].
Input
signals = [5, 5, 5, 5]
Output
[]
Explanation: Index 0: 5 is not strictly greater than 5. Index 1: 5 is not strictly greater than 5. Index 2: 5 is not strictly greater than 5. Index 3: 5 is not strictly greater than 5. No strict inequalities exist. Result: [].
Input
signals = [10]
Output
[0]
Explanation: The array has length 1. By definition, the single element is a peak. Result: [0].
Input
signals = [1, 2, 3, 4, 5]
Output
[4]
Explanation: Index 0: 1 < 2. Index 1: 2 < 1? No, 2 > 1 but 2 < 3. Index 2: 3 < 2? No, 3 > 2 but 3 < 4. Index 3: 4 < 3? No, 4 > 3 but 4 < 5. Index 4: 5 > 4 (boundary condition). Result: [4].
Constraints
- 1 <= signals.length <= 10^5
- -10^9 <= signals[i] <= 10^9
- The input array is not guaranteed to contain distinct values.
Optimal Approach & Strategy
Use a single pass through the array, checking each element against its immediate neighbors. Handle boundary indices by only checking one neighbor. This is the same as the brute force approach but with careful attention to edge cases.
Brute Force Approach
Iterate through each index and check if the value is greater than its neighbors, handling boundary cases separately. This is already O(n) time and O(1) space, so it is optimal.
Verified Code Solutions
function findPeaks(signals) {
const peaks = [];
const n = signals.length;
for(let i=0;i<n;i++){
if(i===0){
if(n===1 || signals[i]>signals[i+1]) peaks.push(i);
}else if(i===n-1){
if(signals[i]>signals[i-1]) peaks.push(i);
}else{
if(signals[i]>signals[i-1] && signals[i]>signals[i+1]) peaks.push(i);
}
}
return peaks;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n = data[0];
const signals = data.slice(1,1+n);
const res = findPeaks(signals);
console.log(res.join(' '));
}
main();#include <bits/stdc++.h>
using namespace std;
vector<int> findPeaks(const vector<int>& signals) {
vector<int> peaks;
int n = signals.size();
for(int i=0;i<n;++i){
if(i==0){
if(n==1 || signals[i]>signals[i+1]) peaks.push_back(i);
}else if(i==n-1){
if(signals[i]>signals[i-1]) peaks.push_back(i);
}else{
if(signals[i]>signals[i-1] && signals[i]>signals[i+1]) 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> signals(n);
for(int i=0;i<n;++i) cin>>signals[i];
vector<int> res=findPeaks(signals);
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> findPeaks(int[] signals) {
List<Integer> peaks = new ArrayList<>();
int n = signals.length;
for(int i=0;i<n;i++){
if(i==0){
if(n==1 || signals[i]>signals[i+1]) peaks.add(i);
}else if(i==n-1){
if(signals[i]>signals[i-1]) peaks.add(i);
}else{
if(signals[i]>signals[i-1] && signals[i]>signals[i+1]) 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[] signals = new int[n];
if(n>0){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) signals[i]=Integer.parseInt(st.nextToken());
}
List<Integer> res = findPeaks(signals);
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 find_peaks(signals):
peaks = []
n = len(signals)
for i in range(n):
if i == 0:
if n == 1 or signals[i] > signals[i+1]:
peaks.append(i)
elif i == n-1:
if signals[i] > signals[i-1]:
peaks.append(i)
else:
if signals[i] > signals[i-1] and signals[i] > signals[i+1]:
peaks.append(i)
return peaks
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
signals = list(map(int, data[1:1+n]))
res = find_peaks(signals)
print(' '.join(map(str, res)))
if __name__ == "__main__":
main()function findPeaks(signals) {
const peaks = [];
const n = signals.length;
for(let i=0;i<n;i++){
if(i===0){
if(n===1 || signals[i]>signals[i+1]) peaks.push(i);
}else if(i===n-1){
if(signals[i]>signals[i-1]) peaks.push(i);
}else{
if(signals[i]>signals[i-1] && signals[i]>signals[i+1]) peaks.push(i);
}
}
return peaks;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
const n = data[0];
const signals = data.slice(1,1+n);
const res = findPeaks(signals);
console.log(res.join(' '));
}
main();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.