Astronomy Duo — Problem Statement & Solution Guide
Problem Description
You are given an array of integers representing the masses of celestial bodies and an integer target representing a desired gravitational pull. Your task is to identify all distinct pairs of indices (i, j) with i < j such that the sum of the masses at those indices equals the target. Return the list of pairs as an array of two‑element arrays, sorted first by the first index and then by the second index. If no such pairs exist, return an empty array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Astronomy Duo"
WHY DOES IT MATTER?
The hash‑map pattern transforms an O(n^2) brute force into linear time, which is critical for real‑world datasets that can contain millions of elements. It also demonstrates a fundamental technique—preprocessing data for constant‑time lookups—that appears in many interview questions and production systems.
OPTIMIZATION CHALLENGE
The core insight is to recognize that the problem is a membership query: does a complement exist? By storing each mass’s indices in a hash map, we reduce the search from linear to constant time per element, cutting the overall complexity from quadratic to linear.
REAL-WORLD CONNECTION
In distributed caching, a key‑value store (like Redis) allows O(1) retrieval of cached results. Similarly, the hash map lets us instantly find a complement without scanning the entire dataset, mirroring how caches accelerate lookups in high‑throughput services.
When explaining this to an interviewer, emphasize the trade‑off: O(n) time vs. O(n) space, and note that if space is at a premium, a sorted two‑pointer approach is a viable alternative.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem is a classic instance of the "two-sum" family: find all index pairs whose values add up to a target. A naive solution examines every pair of indices, yielding an O(n^2) time complexity that quickly becomes infeasible for large arrays (e.g., n=10^5). The optimal paradigm leverages a hash map (or dictionary) to record the indices of each mass as we iterate. For each element a[i], we compute the complement target-a[i] and check if it already exists in the map; if so, we output all stored indices for that complement. This reduces the search for a partner to constant time per element, achieving O(n) time while using O(n) additional space. Sorting followed by a two-pointer sweep is another O(n log n) solution, but the hash map approach is simpler and faster for unsorted input.
The key insight is that the problem reduces to a membership query: does a complement exist? By precomputing and storing indices, we avoid repeated scans. Moreover, because we must return all distinct pairs, we must store *all* indices for each value, not just one, which the hash map naturally supports via lists.
In distributed or large-scale contexts, this pattern mirrors the “map‑reduce” approach: the map phase emits key–value pairs (mass, index), and the reduce phase groups indices by mass, enabling efficient pair generation without pairwise comparison.
Interview Questions on This Problem
Q1How would you modify the algorithm if the array were sorted and you could not use extra space?
You would use the two-pointer technique: start one pointer at the beginning and one at the end, moving them inward based on the sum relative to the target. This gives O(n) time and O(1) space but requires the array to be sorted first, which costs O(n log n) if not already sorted.
Q2In a production system, you need to handle streaming data where masses arrive one by one. How would you adapt the solution?
Maintain a hash map of seen masses to their indices. For each new mass, compute its complement and immediately output any pairs with previously seen indices. This online algorithm runs in O(1) amortized time per element and uses O(n) space for the stream.
Q3What would you do if the array contains duplicate masses and you need to avoid duplicate pairs in the output?
Store indices in the hash map as lists. When generating pairs, iterate over the list of indices for the complement and pair each with the current index, ensuring i<j. To avoid duplicate pairs, only emit pairs where the current index is greater than the stored indices, which naturally enforces uniqueness.
Examples
Input
nums: [1,2,3,4,5], target: 5
Output
[[0,3],[1,2]]
Explanation: The pairs that sum to 5 are: 1 (index 0) + 4 (index 3) and 2 (index 1) + 3 (index 2). They are listed in ascending order of the first index.
Input
nums: [4,1,5,-1,3], target: 4
Output
[[1,4],[2,3]]
Explanation: The valid pairs are 1 (index 1) + 3 (index 4) and 5 (index 2) + (-1) (index 3). They are sorted by the first index.
Input
nums: [10,20,10,30,40], target: 20
Output
[[0,2]]
Explanation: Only the two 10s at indices 0 and 2 sum to 20. No other pair meets the target.
Input
nums: [5,5,5,5], target: 10
Output
[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]
Explanation: Every distinct pair of the four 5s sums to 10, yielding six pairs. They are listed in lexicographic order.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- -2000000000 <= target <= 2000000000
- The total number of returned pairs will not exceed 100000
- Time complexity must be O(n) on average
Optimal Approach & Strategy
Iterate through the array once, storing each mass’s indices in a hash map. For each element, compute the complement target - mass and look it up in the map to find all matching indices, then record the pairs. This runs in O(n) time with O(n) extra space.
Brute Force Approach
Check every pair of indices i < j and compute the sum of masses[i] + masses[j]. If the sum equals the target, record the pair. This requires nested loops and runs in O(n^2) time.
Verified Code Solutions
function findPairs(nums, target){
const map = new Map();
nums.forEach((v,i)=>{
if(!map.has(v)) map.set(v,[]);
map.get(v).push(i);
});
const res=[];
for(let i=0;i<nums.length;i++){
const comp=target-nums[i];
if(map.has(comp)){
for(const j of map.get(comp)) if(j>i) res.push([i,j]);
}
}
return res;
}
const nums=[1,2,3,4,5];
const target=5;
console.log(findPairs(nums,target));#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> findPairs(const vector<int>& nums, int target){
unordered_map<int, vector<int>> mp;
for(int i=0;i<(int)nums.size();++i) mp[nums[i]].push_back(i);
vector<vector<int>> res;
for(int i=0;i<(int)nums.size();++i){
int comp = target - nums[i];
if(mp.count(comp)){
for(int j: mp[comp]) if(j>i) res.push_back({i,j});
}
}
return res;
}
int main(){
vector<int> nums = {1,2,3,4,5};
int target = 5;
auto res = findPairs(nums,target);
for(auto &p: res) cout << '[' << p[0] << ',' << p[1] << '] ';
return 0;
}import java.util.*;
public class Main {
public static List<int[]> findPairs(int[] nums, int target){
Map<Integer, List<Integer>> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
map.computeIfAbsent(nums[i], k->new ArrayList<>()).add(i);
}
List<int[]> res = new ArrayList<>();
for(int i=0;i<nums.length;i++){
int comp = target - nums[i];
if(map.containsKey(comp)){
for(int j: map.get(comp)) if(j>i) res.add(new int[]{i,j});
}
}
return res;
}
public static void main(String[] args){
int[] nums = {1,2,3,4,5};
int target = 5;
List<int[]> res = findPairs(nums, target);
for(int[] p: res) System.out.println("["+p[0]+","+p[1]+"]");
}
}def find_pairs(nums, target):
mp = {}
for i, v in enumerate(nums):
mp.setdefault(v, []).append(i)
res = []
for i, v in enumerate(nums):
comp = target - v
if comp in mp:
for j in mp[comp]:
if j > i:
res.append([i, j])
return res
nums = [1,2,3,4,5]
target = 5
print(find_pairs(nums, target))function findPairs(nums, target){
const map = new Map();
nums.forEach((v,i)=>{
if(!map.has(v)) map.set(v,[]);
map.get(v).push(i);
});
const res=[];
for(let i=0;i<nums.length;i++){
const comp=target-nums[i];
if(map.has(comp)){
for(const j of map.get(comp)) if(j>i) res.push([i,j]);
}
}
return res;
}
const nums=[1,2,3,4,5];
const target=5;
console.log(findPairs(nums,target));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.