Galaxy Expedition — Problem Statement & Solution Guide
Problem Description
Given an integer array representing planetary coordinates of spacecraft, count how many index pairs (i,j) satisfy i<j and the two coordinates are equal. Return the total number of such pairs. An optimal solution runs in O(n) time by storing the frequency of each coordinate in a hash map and summing nC2 for each frequency.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galaxy Expedition"
WHY DOES IT MATTER?
The frequency‑count pattern is a cornerstone for turning quadratic pair‑counting problems into linear ones, a skill that appears repeatedly in coding interviews and real‑world data pipelines.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that the exact positions of equal values are irrelevant—only how many times each value appears matters—allowing us to replace nested comparisons with a single pass and a simple combinatorial formula.
REAL-WORLD CONNECTION
Think of a distributed logging system that needs to know how many servers emitted the same error code at the same time; aggregating counts per code via a hash map mirrors the same optimization.
When presenting the solution, first state the naive O(n^2) idea, then immediately point out the frequency insight and walk through the nC2 calculation; this shows both problem awareness and optimal thinking.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The task is to count all unordered index pairs (i, j) where i < j and the values at those indices are identical. A straightforward solution would compare each element with every later element, leading to O(n^2) time, which quickly becomes infeasible for arrays with millions of entries. This quadratic blow‑up is the classic symptom of a nested‑loop approach that does not exploit any structure in the data.
A far more efficient paradigm leverages the fact that only the frequency of each distinct coordinate matters. By scanning the array once and populating a hash map (or dictionary) where the key is the coordinate and the value is its occurrence count, we can later compute the number of valid pairs for each coordinate using the combinatorial formula nC2 = n·(n‑1)/2. This reduces the overall time to O(n) while using O(k) extra space, where k is the number of unique coordinates, which in the worst case is O(n). The approach exemplifies the “frequency‑count + combinatorial aggregation” pattern that turns many seemingly quadratic problems into linear ones.
Interview Questions on This Problem
Q1At a global product company, how would you design an O(n) solution to count equal‑value index pairs in a large telemetry array?
I would traverse the array once, using a hash map to tally the frequency of each telemetry value. After the pass, I would sum up freq*(freq‑1)/2 for each entry, which directly yields the number of valid pairs.
Q2In a fintech platform, why might counting duplicate transaction timestamps be a risk if you use a naive O(n^2) algorithm?
Financial data streams can contain millions of records per day; a quadratic algorithm would time out or exhaust resources, potentially missing fraud detection windows. The hash‑map frequency method guarantees linear performance regardless of volume.
Q3A high‑growth startup asks you to extend the solution to also return the list of pairs for the most frequent coordinate. How would you modify the linear algorithm?
First, keep the frequency map as before. Identify the maximum frequency, then in a second linear pass collect indices of that coordinate and generate all combinations of those indices; this extra step is O(m) where m is the count of the most frequent value, keeping overall complexity linear for typical data.
Examples
Input
[5,1,3,5,2,5]
Output
3
Explanation: The value 5 occurs at indices 0,3,5. The three possible pairs are (0,3),(0,5),(3,5). No other value repeats, so the answer is 3.
Input
[7,7,7,7]
Output
6
Explanation: Four occurrences of 7 generate C(4,2)=6 distinct pairs: (0,1),(0,2),(0,3),(1,2),(1,3),(2,3).
Input
[0,-1,2,3]
Output
0
Explanation: All coordinates are distinct, therefore no valid pair exists.
Constraints
- 1 <= coords.length <= 200000
- -10^9 <= coords[i] <= 10^9
- Result fits in 64-bit signed integer
Optimal Approach & Strategy
Use a hash map to count occurrences of each coordinate in a single pass, then sum freq*(freq‑1)/2 for all keys. This yields an O(n) time solution with O(n) auxiliary space.
Brute Force Approach
Iterate over every index i and, for each i, loop through all j > i checking if arr[i] == arr[j]; count each match. This double loop runs in O(n^2) time and is impractical for large arrays.
Verified Code Solutions
function countGalaxyPairs(arr) {
const freq = new Map();
for (const val of arr) {
freq.set(val, (freq.get(val) || 0) + 1);
}
let pairs = 0;
for (const count of freq.values()) {
pairs += (count * (count - 1)) / 2;
}
return pairs;
}
const arr = [5, 1, 3, 5, 2, 5];
console.log(countGalaxyPairs(arr));#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
long long countGalaxyPairs(const vector<int>& arr) {
unordered_map<int, long long> freq;
for (int val : arr) {
freq[val]++;
}
long long pairs = 0;
for (const auto& entry : freq) {
long long count = entry.second;
pairs += (count * (count - 1)) / 2;
}
return pairs;
}
int main() {
vector<int> arr = {5, 1, 3, 5, 2, 5};
cout << countGalaxyPairs(arr) << endl;
return 0;
}import java.util.*;
public class Main {
public static long countGalaxyPairs(int[] arr) {
Map<Integer, Long> freq = new HashMap<>();
for (int val : arr) {
freq.put(val, freq.getOrDefault(val, 0L) + 1);
}
long pairs = 0;
for (long count : freq.values()) {
pairs += (count * (count - 1)) / 2;
}
return pairs;
}
public static void main(String[] args) {
int[] arr = {5, 1, 3, 5, 2, 5};
System.out.println(countGalaxyPairs(arr));
}
}from typing import List
def count_galaxy_pairs(arr: List[int]) -> int:
freq = {}
for val in arr:
freq[val] = freq.get(val, 0) + 1
pairs = 0
for count in freq.values():
pairs += (count * (count - 1)) // 2
return pairs
if __name__ == "__main__":
arr = [5, 1, 3, 5, 2, 5]
print(count_galaxy_pairs(arr))function countGalaxyPairs(arr) {
const freq = new Map();
for (const val of arr) {
freq.set(val, (freq.get(val) || 0) + 1);
}
let pairs = 0;
for (const count of freq.values()) {
pairs += (count * (count - 1)) / 2;
}
return pairs;
}
const arr = [5, 1, 3, 5, 2, 5];
console.log(countGalaxyPairs(arr));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.