Astronomical Data Analysis — Problem Statement & Solution Guide
Problem Description
Given an integer array nums that records sequential measurements, identify every position i whose value is not smaller than the values of its immediate neighbours. For the first element (i=0) compare only with nums[1]; for the last element (i=n‑1) compare only with nums[n‑2]; for all other positions compare with both nums[i‑1] and nums[i+1]. Return all qualifying indices in ascending order. The array contains at least one element.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Astronomical Data Analysis"
WHY DOES IT MATTER?
Identifying local maxima/minima is a foundational pattern for signal processing, anomaly detection, and optimization problems; mastering it demonstrates an ability to reason about neighbor relationships efficiently.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that each element’s decision is independent of distant elements, allowing a single linear scan with constant extra memory instead of repeated comparisons or auxiliary data structures.
REAL-WORLD CONNECTION
Think of a network of temperature sensors along a pipeline: detecting points that are hotter than their immediate neighbors helps locate potential leaks or hotspots, mirroring the peak‑finding logic in this problem.
When coding, write the boundary checks first (i==0 or i==n‑1) to avoid index‑out‑of‑range bugs, then handle the generic case; this order keeps the code clean and interviewers happy.
COMPLEXITY AT A GLANCE
O(n)O(1) additional (output list O(k))Core Theory — Why This Approach?
The task is essentially a one‑dimensional peak detection problem. In algorithmic terms we need to scan the array and, for each index, compare its value against its immediate neighbours. A naive solution that checks each element with nested loops would still be linear in time but often leads to redundant boundary checks and can be error‑prone when handling the first and last positions, especially on very large inputs where every extra operation adds up.
The optimal paradigm leverages the fact that each element’s relationship to its neighbours can be decided in O(1) time. By iterating once from left to right, we treat the first and last elements as special cases (they have only one neighbour) and apply a simple two‑sided comparison for all interior indices. This single‑pass approach guarantees linear time while using only constant auxiliary space, making it scalable to arrays with millions of measurements.
Why this matters for large‑scale data: astronomical or sensor streams often contain billions of samples. An O(n) scan with O(1) extra memory fits comfortably in cache, avoids costly random accesses, and can be parallelized if needed. The algorithm’s simplicity also reduces the risk of off‑by‑one bugs, a common source of interview failures.
Interview Questions on This Problem
Q1How would you modify the solution to return the actual peak values instead of their indices, and what impact does this have on complexity?
Simply collect nums[i] instead of i when the condition holds; the time remains O(n) and space stays O(k) for the result, where k is the number of peaks.
Q2In a fintech platform processing tick‑by‑tick price data, why might you prefer this O(1)‑space scan over a segment‑tree based solution?
A segment tree adds O(log n) query overhead and O(n) extra memory, which is unnecessary for a single linear pass; the scan is faster, uses less memory, and is easier to reason about under strict latency constraints.
Q3At a high‑growth startup you need to run this check on a distributed stream. How can you adapt the algorithm for a map‑reduce style pipeline?
Each mapper can emit local peaks with their global index; a reducer then validates boundary elements between partitions, ensuring correctness while preserving overall O(n) work across workers.
Examples
Input
[2,1,2,3,4,4,3]
Output
[0,4,5]
Explanation: Index 0: 2 ≥ 1 → peak. Index 1: 1 < 2 → not a peak. Index 2: 2 < 3 → not a peak. Index 3: 3 < 4 → not a peak. Index 4: 4 ≥ 3 and 4 ≥ 4 → peak. Index 5: 4 ≥ 4 and 4 ≥ 3 → peak. Index 6: 3 < 4 → not a peak. Collected peaks → [0,4,5].
Input
[5]
Output
[0]
Explanation: The single element has no neighbours, so it satisfies the peak condition by definition. Hence index 0 is returned.
Input
[1,3,2,2,3,1]
Output
[1,4]
Explanation: Index 0: 1 < 3 → not a peak. Index 1: 3 ≥ 1 and 3 ≥ 2 → peak. Index 2: 2 < 3 → not a peak. Index 3: 2 < 3 (right neighbour) → not a peak. Index 4: 3 ≥ 2 and 3 ≥ 1 → peak. Index 5: 1 < 3 → not a peak. Peaks are at indices 1 and 4.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- Array contains at least one element
Optimal Approach & Strategy
Perform a single left‑to‑right pass, handling the first and last indices as special cases and using a uniform two‑neighbor comparison for the rest, achieving O(n) time with O(1) auxiliary space.
Brute Force Approach
Check each element against its neighbours using separate if‑statements for every index, potentially re‑checking boundaries multiple times, which still runs in O(n) but is verbose and error‑prone.
Verified Code Solutions
'use strict';
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 findQualifyingIndices(nums) {
const ans = [];
const len = nums.length;
for (let i = 0; i < len; ++i) {
let ok = true;
if (i > 0 && nums[i] < nums[i - 1]) ok = false;
if (i + 1 < len && nums[i] < nums[i + 1]) ok = false;
if (ok) ans.push(i);
}
return ans;
}
const result = findQualifyingIndices(nums);
console.log(result.join(' '));#include <bits/stdc++.h>
using namespace std;
vector<int> findQualifyingIndices(const vector<int>& nums) {
vector<int> ans;
int n = (int)nums.size();
if (n == 0) return ans;
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 = findQualifyingIndices(nums);
for(size_t i = 0; i < res.size(); ++i) {
if(i) cout << ' ';
cout << res[i];
}
cout << '\n';
return 0;
}import java.util.*;
public class Main {
public static List<Integer> findQualifyingIndices(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) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) return;
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
List<Integer> res = findQualifyingIndices(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 find_qualifying_indices(nums):
ans = []
n = len(nums)
for i, val in enumerate(nums):
ok = True
if i > 0 and val < nums[i-1]:
ok = False
if i + 1 < n and val < nums[i+1]:
ok = False
if ok:
ans.append(i)
return ans
def main():
tokens = sys.stdin.read().strip().split()
if not tokens:
return
n = int(tokens[0])
nums = list(map(int, tokens[1:1+n]))
res = find_qualifying_indices(nums)
print(' '.join(map(str, res)))
if __name__ == "__main__":
main()'use strict';
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 findQualifyingIndices(nums) {
const ans = [];
const len = nums.length;
for (let i = 0; i < len; ++i) {
let ok = true;
if (i > 0 && nums[i] < nums[i - 1]) ok = false;
if (i + 1 < len && nums[i] < nums[i + 1]) ok = false;
if (ok) ans.push(i);
}
return ans;
}
const result = findQualifyingIndices(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.