Galaxy Anomaly Detection — Problem Statement & Solution Guide

ArraysMediumSliding Window

TimeO(n)

SpaceO(1)

Problem Description

You are analyzing a sequence of energy flux measurements recorded by a deep-space observatory. The data is stored in an array energyReadings where each element represents the intensity at a specific time interval. A time interval is classified as a 'Galaxy Anomaly' if its energy reading is greater than or equal to the readings of its immediate neighbors. For the first and last elements in the array, only the single existing neighbor is considered for comparison. Your task is to identify all indices corresponding to these anomalies.

Given an integer array energyReadings of length n, return an array of indices i such that energyReadings[i] >= energyReadings[i-1] (if i > 0) and energyReadings[i] >= energyReadings[i+1] (if i < n-1). The returned indices must be in ascending order.

DSA Pattern Breakdown

"Galaxy Anomaly Detection"

medium

WHY DOES IT MATTER?

Peak detection appears in signal processing, stock market analysis, and system health monitoring; recognizing the pattern helps engineers quickly identify local maxima without costly recomputation.

OPTIMIZATION CHALLENGE

The insight is that each element’s status can be decided with constant‑time neighbor checks, so a single pass suffices—no need for auxiliary stacks, segment trees, or extra passes.

REAL-WORLD CONNECTION

Think of a distributed sensor network where each node reports a metric; a node is flagged as anomalous if its reading is not lower than any neighboring node, similar to electing a leader in a ring topology based on highest ID.

During the interview, write the loop that handles three cases (first, middle, last) in one pass; use <= or >= consistently to avoid off‑by‑one bugs, and early‑return for empty arrays.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for identifying "Galaxy Anomalies" – indices i where energyReadings[i] is greater than or equal to its immediate neighbors. This is a classic peak‑finding scenario. A naïve solution scans each element and compares it with its left and right neighbor, which is O(n) time and O(1) space, but many interviewers expect you to discuss why a linear scan is already optimal for a single‑pass count and why more exotic approaches like binary search are unnecessary when only counting peaks. The optimal paradigm leverages a single traversal while handling edge cases (first and last elements have only one neighbor) and avoids extra data structures, yielding O(n) time and O(1) auxiliary space. Understanding this pattern reinforces the principle that sometimes the simplest linear scan is the best answer, especially when the problem does not require locating a specific peak but counting all of them.

Interview Questions on This Problem

Q1How would you modify the solution to return the indices of all Galaxy Anomalies instead of just the count?

Maintain a list (or dynamic array) while scanning; whenever the current element satisfies the >= neighbor condition, push its index onto the list. The overall complexity remains O(n) time and O(k) space where k is the number of peaks.

Q2If the array is sorted in non‑decreasing order, what is the maximum number of Galaxy Anomalies possible?

In a non‑decreasing array only the last element can be >= its left neighbor, so the maximum count is 1. This edge case helps verify that the algorithm correctly handles monotonic sequences.

Q3Can you solve the problem in O(log n) time using a divide‑and‑conquer approach? If so, under what constraints?

A true O(log n) solution is possible only when you need to find a single peak (not count all) and the array has no equal adjacent values; binary‑search‑like logic can locate a peak by comparing mid with its neighbors. Counting all peaks still requires O(n) because every element may need to be examined.

Examples

Example 1

Input

energyReadings = [1, 2, 1, 3, 2]

Output

[1, 3]

Explanation: Index 0: 1 < 2 (neighbor at 1), not an anomaly. Index 1: 2 >= 1 (left) and 2 >= 1 (right), anomaly. Index 2: 1 < 2 (left), not an anomaly. Index 3: 3 >= 1 (left) and 3 >= 2 (right), anomaly. Index 4: 2 < 3 (neighbor at 3), not an anomaly. Result: [1, 3].

Example 2

Input

energyReadings = [5, 5, 5, 5]

Output

[0, 1, 2, 3]

Explanation: Index 0: 5 >= 5 (neighbor at 1), anomaly. Index 1: 5 >= 5 (left) and 5 >= 5 (right), anomaly. Index 2: 5 >= 5 (left) and 5 >= 5 (right), anomaly. Index 3: 5 >= 5 (neighbor at 2), anomaly. Result: [0, 1, 2, 3].

Example 3

Input

energyReadings = [10, 9, 8, 7, 6]

Output

[0]

Explanation: Index 0: 10 >= 9 (neighbor at 1), anomaly. Index 1: 9 < 10 (left), not an anomaly. Index 2: 8 < 9 (left), not an anomaly. Index 3: 7 < 8 (left), not an anomaly. Index 4: 6 < 7 (neighbor at 3), not an anomaly. Result: [0].

Example 4

Input

energyReadings = [3, 1, 4, 1, 5, 9, 2, 6]

Output

[0, 2, 5, 7]

Explanation: Index 0: 3 >= 1 (neighbor at 1), anomaly. Index 1: 1 < 3 (left), not an anomaly. Index 2: 4 >= 1 (left) and 4 >= 1 (right), anomaly. Index 3: 1 < 4 (left), not an anomaly. Index 4: 5 >= 1 (left) and 5 >= 9? No, 5 < 9, not an anomaly. Wait, let's re-evaluate Index 4: Left is 1, Right is 9. 5 >= 1 is true, 5 >= 9 is false. So not an anomaly. Index 5: 9 >= 5 (left) and 9 >= 2 (right), anomaly. Index 6: 2 < 9 (left), not an anomaly. Index 7: 6 >= 2 (neighbor at 6), anomaly. Result: [0, 2, 5, 7].

Constraints

1 <= energyReadings.length <= 10^5
-10^9 <= energyReadings[i] <= 10^9

Optimal Approach & Strategy

Perform a single linear pass, comparing each element with at most two neighbors, achieving O(n) time and O(1) extra space.

Brute Force Approach

Check every element against its neighbors using nested loops or repeated scans, leading to O(n^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} energyReadings
 * @return {number[]}
 */
function findGalaxyAnomalies(energyReadings) {
    const n = energyReadings.length;
    const anomalies = [];
    
    if (n === 0) {
        return anomalies;
    }
    
    // Check first element
    if (n === 1 || energyReadings[0] >= energyReadings[1]) {
        anomalies.push(0);
    }
    
    // Check middle elements
    for (let i = 1; i < n - 1; i++) {
        if (energyReadings[i] >= energyReadings[i - 1] && energyReadings[i] >= energyReadings[i + 1]) {
            anomalies.push(i);
        }
    }
    
    // Check last element
    if (n > 1 && energyReadings[n - 1] >= energyReadings[n - 2]) {
        anomalies.push(n - 1);
    }
    
    return anomalies;
}

// Driver code for testing
const readings = [1, 2, 1, 3, 2];
const result = findGalaxyAnomalies(readings);
console.log(result.join(", "));
module.exports = findGalaxyAnomalies;

#include <iostream>
#include <vector>

using namespace std;

vector<int> findGalaxyAnomalies(vector<int>& energyReadings) {
    int n = energyReadings.size();
    vector<int> anomalies;
    
    if (n == 0) {
        return anomalies;
    }
    
    // Check first element
    if (n == 1 || energyReadings[0] >= energyReadings[1]) {
        anomalies.push_back(0);
    }
    
    // Check middle elements
    for (int i = 1; i < n - 1; i++) {
        if (energyReadings[i] >= energyReadings[i - 1] && energyReadings[i] >= energyReadings[i + 1]) {
            anomalies.push_back(i);
        }
    }
    
    // Check last element
    if (n > 1 && energyReadings[n - 1] >= energyReadings[n - 2]) {
        anomalies.push_back(n - 1);
    }
    
    return anomalies;
}

int main() {
    vector<int> readings = {1, 2, 1, 3, 2};
    vector<int> result = findGalaxyAnomalies(readings);
    
    for (int i = 0; i < result.size(); i++) {
        if (i > 0) cout << ", ";
        cout << result[i];
    }
    cout << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    public static int[] findGalaxyAnomalies(int[] energyReadings) {
        int n = energyReadings.length;
        List<Integer> anomalies = new ArrayList<>();
        
        if (n == 0) {
            return new int[0];
        }
        
        // Check first element
        if (n == 1 || energyReadings[0] >= energyReadings[1]) {
            anomalies.add(0);
        }
        
        // Check middle elements
        for (int i = 1; i < n - 1; i++) {
            if (energyReadings[i] >= energyReadings[i - 1] && energyReadings[i] >= energyReadings[i + 1]) {
                anomalies.add(i);
            }
        }
        
        // Check last element
        if (n > 1 && energyReadings[n - 1] >= energyReadings[n - 2]) {
            anomalies.add(n - 1);
        }
        
        int[] result = new int[anomalies.size()];
        for (int i = 0; i < anomalies.size(); i++) {
            result[i] = anomalies.get(i);
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] readings = {1, 2, 1, 3, 2};
        int[] result = findGalaxyAnomalies(readings);
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < result.length; i++) {
            if (i > 0) sb.append(", ");
            sb.append(result[i]);
        }
        System.out.println(sb.toString());
    }
}

from typing import List

def findGalaxyAnomalies(energyReadings: List[int]) -> List[int]:
    n = len(energyReadings)
    anomalies = []
    
    if n == 0:
        return anomalies
    
    # Check first element
    if n == 1 or energyReadings[0] >= energyReadings[1]:
        anomalies.append(0)
    
    # Check middle elements
    for i in range(1, n - 1):
        if energyReadings[i] >= energyReadings[i - 1] and energyReadings[i] >= energyReadings[i + 1]:
            anomalies.append(i)
    
    # Check last element
    if n > 1 and energyReadings[n - 1] >= energyReadings[n - 2]:
        anomalies.append(n - 1)
    
    return anomalies

# Driver code for testing
if __name__ == "__main__":
    readings = [1, 2, 1, 3, 2]
    result = findGalaxyAnomalies(readings)
    print(result)

/**
 * @param {number[]} energyReadings
 * @return {number[]}
 */
function findGalaxyAnomalies(energyReadings) {
    const n = energyReadings.length;
    const anomalies = [];
    
    if (n === 0) {
        return anomalies;
    }
    
    // Check first element
    if (n === 1 || energyReadings[0] >= energyReadings[1]) {
        anomalies.push(0);
    }
    
    // Check middle elements
    for (let i = 1; i < n - 1; i++) {
        if (energyReadings[i] >= energyReadings[i - 1] && energyReadings[i] >= energyReadings[i + 1]) {
            anomalies.push(i);
        }
    }
    
    // Check last element
    if (n > 1 && energyReadings[n - 1] >= energyReadings[n - 2]) {
        anomalies.push(n - 1);
    }
    
    return anomalies;
}

// Driver code for testing
const readings = [1, 2, 1, 3, 2];
const result = findGalaxyAnomalies(readings);
console.log(result.join(", "));
module.exports = findGalaxyAnomalies;

Asked in Top Tech Interviews

PayPalPhonePe

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.

Galaxy Anomaly Detection Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Galaxy Anomaly Detection — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor