Loading…

mediumGraphsSometimes asked

Journey to the Moon

Q: How do you solve Journey to the Moon using the DFS / BFS Component Sizes + Complement (Baseline) approach?

When to use it: A clean first cut: flood-fill to get the size of every country, then apply C(N,2) − Σ C(sᵢ,2). Correct and easy to explain. The problem only depends on country *sizes*, so the graph work is reduced to component sizing — then it is pure combinatorics. **Why complementary counting.** Counting cross-country pairs directly means, for each astronaut, adding up everyone in every *other* country — awkward and easy to double-count. The complement is trivial: the only forbidden pairs are within a single country, and a country of size `s` contributes exactly `C(s,2) = s(s−1)/2` such pairs. So the answer is `C(N,2) − Σ C(sᵢ,2)`. **Why flood fill gives the sizes.** From any unvisited astronaut, walk the whole component, counting nodes. Each astronaut is visited exactly once, so the sizes partition all `N` astronauts — including singletons, which are countries of one and still pair with everyone outside. **Why the traversal must be iterative.** With `N` up to `10⁵`, a long chain of same-country relations can be `10⁵` deep. A recursive DFS would nest that many frames and overflow the call stack, so use an explicit stack (or a BFS queue). The visiting order is irrelevant to the sizes. **Why long, not int.** `C(N,2)` for `N = 10⁵` is about `5 × 10⁹`, which silently wraps in a 32-bit int. Keep the total and all products in `long`. Time complexity: O(N + E). Space complexity: O(N + E).

Q: How do you solve Journey to the Moon using the Union-Find Sizes + Running-Sum Accumulation (Optimal) approach?

When to use it: The cleanest connectivity-only answer. Union each pair, read off component sizes from the roots, and accumulate cross pairs with answer += size × seen — no giant C(N,2) intermediate. Union-Find is the right structure when only connectivity matters — it groups astronauts without ever building paths. **Building the countries.** Start every astronaut in its own set. For each pair `[a, b]`, `union` them. After all pairs, two astronauts share a root exactly when a chain of same-country relations links them — the transitivity of the relation falls out of the merging for free. The `size[]` array on each root gives each country's headcount. **Path compression and union by rank.** A naïve `find` can walk an `O(N)` chain; compressing the path during `find` and attaching the shorter tree under the taller one pin each operation at `O(α(N))` — at most about 4 for any realistic input. The `find` loop is a `while`, never recursive, so deep groups cannot overflow the stack. **The running-sum trick.** Instead of computing `C(N,2)` and subtracting, count cross pairs directly as you sweep the component sizes. Keep `seen` = astronauts processed so far. When you reach a country of size `s`, every astronaut in it pairs with every one of the `seen` astronauts already counted (all in other countries), adding `s × seen` valid pairs. Then do `seen += s`. After the sweep, `seen == N` and the accumulated total is the answer. This never forms the large `C(N,2)` value, which keeps intermediate magnitudes smaller and the logic harder to get wrong. **Why this equals the complement formula.** Summing `s × seen` over countries counts each cross-country pair exactly once — the later country contributes the pair against every earlier astronaut. That is algebraically identical to `C(N,2) − Σ C(sᵢ,2)`; the running form is just a tidier way to evaluate it. Either way, use `long`. Time complexity: O(N + E·α(N)). Space complexity: O(N).

Graphs · 26 of 34 · 11 min

There are N astronauts numbered 0 to N − 1. A list of pairs tells you which astronauts are from the same country: pairs[i] = [a, b] means astronaut a and astronaut b share a country (this relation is transitive — if a and b are countrymen and b and c are, then so are a and c).

The space agency wants to send two astronauts from different countries to the moon. Return the number of ways to choose such a pair.

In plain English

Group the astronauts by country: each connected component of the 'same-country' graph is one country. Two astronauts can travel together only if they belong to different components. Counting those cross-component pairs directly is fiddly, but the total number of pairs is just C(N,2) and the disallowed (same-country) pairs are the sum of C(sᵢ,2) over components. Subtract the second from the first.

Examples

Example 1

Input: N = 5, pairs = [[0,1],[2,3],[0,4]]
Output: 6
Note: Countries: {0,1,4} (size 3) and {2,3} (size 2). Total C(5,2)=10; same-country C(3,2)+C(2,2)=3+1=4; answer 10−4=6.

Example 2

Input: N = 4, pairs = [[0,2]]
Output: 5
Note: Countries: {0,2} (size 2), {1} (size 1), {3} (size 1). Total C(4,2)=6; same-country C(2,2)=1; answer 6−1=5.

Example 3

Input: N = 3, pairs = [[0,1]]
Output: 2
Note: Countries: {0,1} (size 2), {2} (size 1). Total C(3,2)=3; same-country 1; answer 2. Astronaut 2 pairs with 0 and 1.

Constraints

1 ≤ N ≤ 10⁵
1 ≤ pairs.length ≤ 10⁴ (each known same-country relation)
0 ≤ a, b < N, a ≠ b
The same-country relation is transitive (it forms connected components)
The answer can exceed 32-bit range — use 64-bit

Clarifying questions4First question: Are astronauts 0-indexed?Explore questions

Q1.Are astronauts 0-indexed?
Yes, 0 to N − 1. Union-Find arrays are sized to N directly.
Q2.Is the same-country relation transitive?
Yes — that is why components model countries. If a-b and b-c are countrymen, a and c are too, even without an explicit pair.
Q3.Do astronauts with no listed pair still count?
Absolutely. An astronaut never mentioned is a country of one — a size-1 component — and pairs with everyone outside it.
Q4.How large can the answer get?
Up to roughly C(10⁵, 2) ≈ 5 × 10⁹, which overflows a 32-bit int. Use long throughout.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Astronauts in the same connected component share a country. Count pairs from different countries = (total pairs) − (same-country pairs). Use Union-Find to get each component's size sᵢ, then answer = C(N,2) − Σ C(sᵢ,2). Equivalently, accumulate cross pairs as you go: for each size s, answer += s × (astronauts seen so far). O(N + E).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe 'pairs from different countries' as total minus same-country pairs, compute component sizes with Union-Find, and guard against 32-bit overflow.

Where candidates slip

Counting same-country pairs as the answer instead of its complement, forgetting isolated astronauts as size-1 components, or overflowing int on C(N,2).

How to stand out

Use complementary counting, present the running-sum accumulation that sidesteps the big C(N,2) intermediate, and state the long-vs-int overflow concern unprompted.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	DFS / BFS Component Sizes + Complement (Baseline)	`O(N + E)`	`O(N + E)`	A clean first cut: flood-fill to get the size of every country, then apply C(N,2) − Σ C(sᵢ,2). Correct and easy to explain.	Read
2	Union-Find Sizes + Running-Sum Accumulation (Optimal)Optimal	`O(N + E·α(N))`	`O(N)`	The cleanest connectivity-only answer. Union each pair, read off component sizes from the roots, and accumulate cross pairs with answer += size × seen — no giant C(N,2) intermediate.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Astronauts grouped into countries

How to read it:Components {0,1,4} and {2,3}. Valid pairs cross the boundary between them.

Rendering diagram…

Complementary counting

How to read it:Subtract the easy-to-count same-country pairs from all pairs.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

DFS / BFS Component Sizes + Complement (Baseline)

TimeO(N + E)SpaceO(N + E)

A clean first cut: flood-fill to get the size of every country, then apply C(N,2) − Σ C(sᵢ,2). Correct and easy to explain.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What single fact about each country do you actually need to count pairs? Not who is in it — just how many.

2Hint 2Explore hint

Build an adjacency list from the pairs and flood-fill each unvisited astronaut to measure its component size.

3Hint 3Explore hint

Total pairs are C(N,2). Pairs inside a country of size s are C(s,2). Subtract the sum of those from the total.

A · Core idea

The problem only depends on country sizes, so the graph work is reduced to component sizing — then it is pure combinatorics.

Why complementary counting. Counting cross-country pairs directly means, for each astronaut, adding up everyone in every other country — awkward and easy to double-count. The complement is trivial: the only forbidden pairs are within a single country, and a country of size s contributes exactly C(s,2) = s(s−1)/2 such pairs. So the answer is C(N,2) − Σ C(sᵢ,2).

Why flood fill gives the sizes. From any unvisited astronaut, walk the whole component, counting nodes. Each astronaut is visited exactly once, so the sizes partition all N astronauts — including singletons, which are countries of one and still pair with everyone outside.

Why the traversal must be iterative. With N up to 10⁵, a long chain of same-country relations can be 10⁵ deep. A recursive DFS would nest that many frames and overflow the call stack, so use an explicit stack (or a BFS queue). The visiting order is irrelevant to the sizes.

Why long, not int. C(N,2) for N = 10⁵ is about 5 × 10⁹, which silently wraps in a 32-bit int. Keep the total and all products in long.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 5, pairs = [[0,1],[2,3],[0,4]]

Interactive diagram

Flood fill sizing one country

flood from 0

Active call / nodeSupporting contextReturned stateNot active

Starting at astronaut 0, the walk reaches 1 and 4 — size 3.

Final result6

C · Code with teaching comments

Reference implementation previewpublic long journeyToMoon(int n, int[][] pairs) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] p : pairs) { adj.get(p[0]).add(p[1]);Explore the full code

solution.javaJava

DFS / BFS Component Sizes + Complement (Baseline) — reference

3 teaching notes

1
public long journeyToMoon(int n, int[][] pairs) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
4
    for (int[] p : pairs) {
5
        adj.get(p[0]).add(p[1]);
6
        adj.get(p[1]).add(p[0]);
7
    }
8
    boolean[] visited = new boolean[n];
9
    // All pairs C(N,2); the long cast prevents overflow before the division.
10
    long total = (long) n * (n - 1) / 2;
11
    long sameCountry = 0;
12
    for (int start = 0; start < n; start++) {
13
        if (visited[start]) continue;
14
        long size = 0;
15
        Deque<Integer> stack = new ArrayDeque<>();
16
        stack.push(start);
17
        visited[start] = true;
18
        // Explicit stack keeps depth on the heap — safe for a 10⁵-deep chain of
19
        // countrymen.
20
        while (!stack.isEmpty()) {           // iterative DFS, no stack overflow
21
            int u = stack.pop();
22
            size++;
23
            for (int v : adj.get(u)) {
24
                if (!visited[v]) {
25
                    visited[v] = true;
26
                    stack.push(v);
27
                }
28
            }
29
        }
30
        // C(size,2) forbidden pairs inside this country, accumulated across components.
31
        sameCountry += size * (size - 1) / 2;
32
    }
33
    return total - sameCountry;
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(N + E) timeO(N + E) spaceOpen the invariant and proofExplore the proof

Reframing 'different country' as 'all pairs minus same country' converts a tangled direct count into one subtraction. The graph reduces to a list of sizes; everything else is arithmetic.

ComplexityO(N + E) time, O(N + E) space — Adjacency list and flood fill each touch every vertex and edge once → O(N + E). The per-component arithmetic and the final subtraction are O(number of components) ≤ O(N).

E · Edge cases and pitfalls3Recursive DFS on a long chain of countrymen — stack overflow at 10⁵ nodes.Explore edge cases

Pitfalls

Recursive DFS on a long chain of countrymen — stack overflow at 10⁵ nodes.
Computing C(N,2) in int — overflows around N ≈ 65000.
Forgetting that isolated astronauts are size-1 components that still pair outward.

03.2

Approach 2 of 2 · Optimal

Union-Find Sizes + Running-Sum Accumulation (Optimal)

TimeO(N + E·α(N))SpaceO(N)

The cleanest connectivity-only answer. Union each pair, read off component sizes from the roots, and accumulate cross pairs with answer += size × seen — no giant C(N,2) intermediate.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You never need the relations after grouping — only the size of each country. What near-constant-time structure tracks 'are these two in the same group' and the group sizes?

2Hint 2Explore hint

Union-Find with path compression and union by rank. After unioning all pairs, each root carries its component size.

3Hint 3Explore hint

Walk the component sizes once. Keep a running 'astronauts seen so far'. Each new country of size s adds s × seen valid pairs (it pairs with everyone already counted).

A · Core idea

Union-Find is the right structure when only connectivity matters — it groups astronauts without ever building paths.

Building the countries. Start every astronaut in its own set. For each pair [a, b], union them. After all pairs, two astronauts share a root exactly when a chain of same-country relations links them — the transitivity of the relation falls out of the merging for free. The size[] array on each root gives each country's headcount.

Path compression and union by rank. A naïve find can walk an O(N) chain; compressing the path during find and attaching the shorter tree under the taller one pin each operation at O(α(N)) — at most about 4 for any realistic input. The find loop is a while, never recursive, so deep groups cannot overflow the stack.

The running-sum trick. Instead of computing C(N,2) and subtracting, count cross pairs directly as you sweep the component sizes. Keep seen = astronauts processed so far. When you reach a country of size s, every astronaut in it pairs with every one of the seen astronauts already counted (all in other countries), adding s × seen valid pairs. Then do seen += s. After the sweep, seen == N and the accumulated total is the answer. This never forms the large C(N,2) value, which keeps intermediate magnitudes smaller and the logic harder to get wrong.

Why this equals the complement formula. Summing s × seen over countries counts each cross-country pair exactly once — the later country contributes the pair against every earlier astronaut. That is algebraically identical to C(N,2) − Σ C(sᵢ,2); the running form is just a tidier way to evaluate it. Either way, use long.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 5, pairs = [[0,1],[2,3],[0,4]]

Interactive diagram

Disjoint-set forest after unions

union 0-1, 2-3, 0-4

Active call / nodeSupporting contextReturned stateNot active

Two countries: {0,1,4} rooted at 0 (size 3) and {2,3} rooted at 2 (size 2).

Final result6

C · Code with teaching comments

solution.javaJava

Union-Find Sizes + Running-Sum Accumulation (Optimal) — optimal

4 teaching notes

1
public long journeyToMoon(int n, int[][] pairs) {
2
    int[] parent = new int[n];
3
    int[] rank = new int[n];
4
    int[] size = new int[n];
5
    for (int i = 0; i < n; i++) {
6
        parent[i] = i;
7
        size[i] = 1;
8
    }
9
    for (int[] p : pairs) {
10
        union(parent, rank, size, p[0], p[1]);
11
    }
12
    long answer = 0;
13
    long seen = 0;
14
    for (int i = 0; i < n; i++) {
15
        // Process each component once, at its root, where the correct size lives.
16
        if (find(parent, i) == i) {          // i is a root → one country
17
            long s = size[i];
18
            // This country's s members each pair with every previously counted
19
            // astronaut.
20
            answer += s * seen;              // pairs with all earlier astronauts
21
            // Grow the running total so the next country pairs against this one too.
22
            seen += s;
23
        }
24
    }
25
    return answer;
26
}
27
 
28
private int find(int[] parent, int x) {
29
    while (parent[x] != x) {
30
        // Compress while climbing; the loop is stack-safe for deep groups.
31
        parent[x] = parent[parent[x]];        // path halving, iterative
32
        x = parent[x];
33
    }
34
    return x;
35
}
36
 
37
private void union(int[] parent, int[] rank, int[] size, int a, int b) {
38
    int ra = find(parent, a), rb = find(parent, b);
39
    if (ra == rb) return;
40
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
41
    parent[rb] = ra;
42
    size[ra] += size[rb];
43
    if (rank[ra] == rank[rb]) rank[ra]++;
44
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.44 lines

D · Why it works and complexityO(N + E·α(N)) timeO(N) spaceOpen the invariant and proofExplore the proof

Two ideas combine: Union-Find reduces the graph to a list of sizes in near-linear time, and the running-sum s × seen accumulation counts cross pairs without ever materializing the quadratic total. The second is a reusable counting pattern whenever you tally pairs across disjoint groups.

ComplexityO(N + E·α(N)) time, O(N) space — Each union/find is O(α(N)), effectively constant, so processing E pairs is O(E·α(N)). Reading sizes is O(N·α(N)). The running-sum sweep is O(number of components). Space is O(N) for parent and size arrays.

E · Edge cases and pitfalls7N = 1, pairs = [] — One astronaut, no possible pair → C(1,2) = 0. answer = 0.Explore edge cases

Edge cases handled

N = 1, pairs = []One astronaut, no possible pair → C(1,2) = 0. answer = 0.
all astronauts same countryOne component of size N. seen stays 0 through the single country → answer 0; no cross pairs exist.
no pairs at allN singleton countries → answer = C(N,2); every pair is cross-country.

Pitfalls

Returning same-country pairs instead of their complement.
Accumulating in int — answer up to 5 × 10⁹ overflows; use long.
Counting size off non-root nodes — only the root holds the true component size.
Recursive find on a deep group — risks stack overflow; use the iterative loop.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long journeyToMoon(int n, int[][] pairs) { int[] parent = new int[n]; int[] rank = new int[n]; int[] size = new int[n]; for (int i = 0; i < n; i++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public long journeyToMoon(int n, int[][] pairs) {
    int[] parent = new int[n];
    int[] rank = new int[n];
    int[] size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    for (int[] p : pairs) {
        union(parent, rank, size, p[0], p[1]);
    }
    long answer = 0;
    long seen = 0;
    for (int i = 0; i < n; i++) {
        if (find(parent, i) == i) {          // i is a root → one country
            long s = size[i];
            answer += s * seen;              // pairs with all earlier astronauts
            seen += s;
        }
    }
    return answer;
}

private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];        // path halving, iterative
        x = parent[x];
    }
    return x;
}

private void union(int[] parent, int[] rank, int[] size, int a, int b) {
    int ra = find(parent, a), rb = find(parent, b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;
    size[ra] += size[rb];
    if (rank[ra] == rank[rb]) rank[ra]++;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning same-country pairs

The question asks for pairs from DIFFERENT countries. Summing C(sᵢ,2) gives the forbidden same-country pairs — the exact opposite of the answer.

Explore the code comparison

Don't write this

return sum(s * (s - 1) // 2 for s in sizes)   # same-country pairs

Write this instead

total = n * (n - 1) // 2
return total - sum(s * (s - 1) // 2 for s in sizes)

32-bit overflow on C(N,2)

For N = 10⁵, n*(n-1)/2 ≈ 5 × 10⁹, far beyond int's 2.1 × 10⁹ ceiling. The product n*(n-1) overflows before the division.

Explore the code comparison

Don't write this

int total = n * (n - 1) / 2;          // n*(n-1) overflows int

Write this instead

long total = (long) n * (n - 1) / 2;  // promote before multiplying

Missing isolated astronauts

An astronaut never named in any pair forms a country of one and pairs with everyone else. Only iterating over astronauts that appear in pairs drops these singletons and undercounts.

Explore the code comparison

Don't write this

for a, b in pairs:        # only touches astronauts that appear in a pair
    union(a, b)
sizes = component_sizes_of_seen_nodes()

Write this instead

parent = list(range(n))   # every astronaut 0..n-1 starts as its own country
for a, b in pairs:
    union(a, b)
# sweep all n astronauts, including untouched singletons

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Component sizes via Union-Find, then complementary counting

Code pattern to memorize

sizes = component sizes from union-find
# complementary form
answer = N*(N-1)/2 - sum(s*(s-1)/2 for s in sizes)
# running-sum form (no big intermediate)
seen = 0; answer = 0
for s in sizes:
    answer += s * seen
    seen += s

Rules to remember

1Two astronauts in the same component are the same country — never a valid pair. Count its complement.
2Use long: with N up to 10⁵, C(N,2) is about 5 × 10⁹, well past 32-bit range.
3Every astronaut counts, including isolated ones — they are singleton components of size 1.
4The running-sum form answer += s × seen avoids forming the huge C(N,2) and is overflow-friendlier.
5Pick Union-Find for connectivity-only counting; you never need paths, just group sizes.

Use this pattern when

Count cross-group pairs when items split into disjoint groups
Connectivity defines the groups (a relation that is symmetric and transitive)
You need group **sizes**, not paths or distances
Complementary counting (total − unwanted) is simpler than counting wanted directly

Choose another pattern when

You need the actual partner pairs, not the count → enumerate, but that is O(N²)
Groups overlap or an item belongs to many → not disjoint sets
You need shortest distance between astronauts → BFS, not component sizing
Pairs must satisfy extra constraints beyond 'different country' → counting gets case-specific

Interview takeaway

When direct counting is messy, count the complement. Same-country pairs are easy (sum of C(sᵢ,2) over components), so subtract them from all pairs. Union-Find delivers the sizes in near-linear time.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternComponent Sizes + Complementary Pair Counting. Recognize it when you must count pairs across disjoint groups: compute group sizes with Union-Find, then either subtract Σ C(sᵢ,2) from C(N,2) or accumulate s × seen. The same size-then-combinatorics shape appears in Roads and Libraries and Components in a Graph.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of Connected Components
The same Union-Find grouping, returning the component count instead of a pair tally.
Components in a Graph
Report smallest and largest component sizes — another read off the same size array.
Roads and Libraries
Per-component greedy cost instead of a pair count, again powered by component sizes.
Count of Pairs With Given Property
Coming soon
Generalized cross-group pair counting with the running-sum s × seen accumulation.

Same pattern

←

Find the Nearest Clone

Continue · Next problem

Roads and Libraries

mediumGraphsSometimes asked

Journey to the Moon

Graphs · 26 of 34 · 11 min

The space agency wants to send two astronauts from different countries to the moon. Return the number of ways to choose such a pair.

In plain English

Examples

Example 1

Input: N = 5, pairs = [[0,1],[2,3],[0,4]]
Output: 6
Note: Countries: {0,1,4} (size 3) and {2,3} (size 2). Total C(5,2)=10; same-country C(3,2)+C(2,2)=3+1=4; answer 10−4=6.

Example 2

Input: N = 4, pairs = [[0,2]]
Output: 5
Note: Countries: {0,2} (size 2), {1} (size 1), {3} (size 1). Total C(4,2)=6; same-country C(2,2)=1; answer 6−1=5.

Example 3

Input: N = 3, pairs = [[0,1]]
Output: 2
Note: Countries: {0,1} (size 2), {2} (size 1). Total C(3,2)=3; same-country 1; answer 2. Astronaut 2 pairs with 0 and 1.

Constraints

1 ≤ N ≤ 10⁵
1 ≤ pairs.length ≤ 10⁴ (each known same-country relation)
0 ≤ a, b < N, a ≠ b
The same-country relation is transitive (it forms connected components)
The answer can exceed 32-bit range — use 64-bit

Clarifying questions4First question: Are astronauts 0-indexed?Explore questions

Q1.Are astronauts 0-indexed?
Yes, 0 to N − 1. Union-Find arrays are sized to N directly.
Q2.Is the same-country relation transitive?
Yes — that is why components model countries. If a-b and b-c are countrymen, a and c are too, even without an explicit pair.
Q3.Do astronauts with no listed pair still count?
Absolutely. An astronaut never mentioned is a country of one — a size-1 component — and pairs with everyone outside it.
Q4.How large can the answer get?
Up to roughly C(10⁵, 2) ≈ 5 × 10⁹, which overflows a 32-bit int. Use long throughout.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe 'pairs from different countries' as total minus same-country pairs, compute component sizes with Union-Find, and guard against 32-bit overflow.

Where candidates slip

Counting same-country pairs as the answer instead of its complement, forgetting isolated astronauts as size-1 components, or overflowing int on C(N,2).

How to stand out

Use complementary counting, present the running-sum accumulation that sidesteps the big C(N,2) intermediate, and state the long-vs-int overflow concern unprompted.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	DFS / BFS Component Sizes + Complement (Baseline)	`O(N + E)`	`O(N + E)`	A clean first cut: flood-fill to get the size of every country, then apply C(N,2) − Σ C(sᵢ,2). Correct and easy to explain.	Read
2	Union-Find Sizes + Running-Sum Accumulation (Optimal)Optimal	`O(N + E·α(N))`	`O(N)`	The cleanest connectivity-only answer. Union each pair, read off component sizes from the roots, and accumulate cross pairs with answer += size × seen — no giant C(N,2) intermediate.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Astronauts grouped into countries

How to read it:Components {0,1,4} and {2,3}. Valid pairs cross the boundary between them.

Rendering diagram…

Complementary counting

How to read it:Subtract the easy-to-count same-country pairs from all pairs.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

DFS / BFS Component Sizes + Complement (Baseline)

TimeO(N + E)SpaceO(N + E)

A clean first cut: flood-fill to get the size of every country, then apply C(N,2) − Σ C(sᵢ,2). Correct and easy to explain.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What single fact about each country do you actually need to count pairs? Not who is in it — just how many.

2Hint 2Explore hint

Build an adjacency list from the pairs and flood-fill each unvisited astronaut to measure its component size.

3Hint 3Explore hint

Total pairs are C(N,2). Pairs inside a country of size s are C(s,2). Subtract the sum of those from the total.

A · Core idea

The problem only depends on country sizes, so the graph work is reduced to component sizing — then it is pure combinatorics.

Why long, not int. C(N,2) for N = 10⁵ is about 5 × 10⁹, which silently wraps in a 32-bit int. Keep the total and all products in long.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 5, pairs = [[0,1],[2,3],[0,4]]

Interactive diagram

Flood fill sizing one country

flood from 0

Active call / nodeSupporting contextReturned stateNot active

Starting at astronaut 0, the walk reaches 1 and 4 — size 3.

Final result6

C · Code with teaching comments

solution.javaJava

DFS / BFS Component Sizes + Complement (Baseline) — reference

3 teaching notes

1
public long journeyToMoon(int n, int[][] pairs) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
4
    for (int[] p : pairs) {
5
        adj.get(p[0]).add(p[1]);
6
        adj.get(p[1]).add(p[0]);
7
    }
8
    boolean[] visited = new boolean[n];
9
    // All pairs C(N,2); the long cast prevents overflow before the division.
10
    long total = (long) n * (n - 1) / 2;
11
    long sameCountry = 0;
12
    for (int start = 0; start < n; start++) {
13
        if (visited[start]) continue;
14
        long size = 0;
15
        Deque<Integer> stack = new ArrayDeque<>();
16
        stack.push(start);
17
        visited[start] = true;
18
        // Explicit stack keeps depth on the heap — safe for a 10⁵-deep chain of
19
        // countrymen.
20
        while (!stack.isEmpty()) {           // iterative DFS, no stack overflow
21
            int u = stack.pop();
22
            size++;
23
            for (int v : adj.get(u)) {
24
                if (!visited[v]) {
25
                    visited[v] = true;
26
                    stack.push(v);
27
                }
28
            }
29
        }
30
        // C(size,2) forbidden pairs inside this country, accumulated across components.
31
        sameCountry += size * (size - 1) / 2;
32
    }
33
    return total - sameCountry;
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(N + E) timeO(N + E) spaceOpen the invariant and proofExplore the proof

Reframing 'different country' as 'all pairs minus same country' converts a tangled direct count into one subtraction. The graph reduces to a list of sizes; everything else is arithmetic.

E · Edge cases and pitfalls3Recursive DFS on a long chain of countrymen — stack overflow at 10⁵ nodes.Explore edge cases

Pitfalls

Recursive DFS on a long chain of countrymen — stack overflow at 10⁵ nodes.
Computing C(N,2) in int — overflows around N ≈ 65000.
Forgetting that isolated astronauts are size-1 components that still pair outward.

03.2

Approach 2 of 2 · Optimal

Union-Find Sizes + Running-Sum Accumulation (Optimal)

TimeO(N + E·α(N))SpaceO(N)

The cleanest connectivity-only answer. Union each pair, read off component sizes from the roots, and accumulate cross pairs with answer += size × seen — no giant C(N,2) intermediate.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You never need the relations after grouping — only the size of each country. What near-constant-time structure tracks 'are these two in the same group' and the group sizes?

2Hint 2Explore hint

Union-Find with path compression and union by rank. After unioning all pairs, each root carries its component size.

3Hint 3Explore hint

Walk the component sizes once. Keep a running 'astronauts seen so far'. Each new country of size s adds s × seen valid pairs (it pairs with everyone already counted).

A · Core idea

Union-Find is the right structure when only connectivity matters — it groups astronauts without ever building paths.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 5, pairs = [[0,1],[2,3],[0,4]]

Interactive diagram

Disjoint-set forest after unions

union 0-1, 2-3, 0-4

Active call / nodeSupporting contextReturned stateNot active

Two countries: {0,1,4} rooted at 0 (size 3) and {2,3} rooted at 2 (size 2).

Final result6

C · Code with teaching comments

solution.javaJava

Union-Find Sizes + Running-Sum Accumulation (Optimal) — optimal

4 teaching notes

1
public long journeyToMoon(int n, int[][] pairs) {
2
    int[] parent = new int[n];
3
    int[] rank = new int[n];
4
    int[] size = new int[n];
5
    for (int i = 0; i < n; i++) {
6
        parent[i] = i;
7
        size[i] = 1;
8
    }
9
    for (int[] p : pairs) {
10
        union(parent, rank, size, p[0], p[1]);
11
    }
12
    long answer = 0;
13
    long seen = 0;
14
    for (int i = 0; i < n; i++) {
15
        // Process each component once, at its root, where the correct size lives.
16
        if (find(parent, i) == i) {          // i is a root → one country
17
            long s = size[i];
18
            // This country's s members each pair with every previously counted
19
            // astronaut.
20
            answer += s * seen;              // pairs with all earlier astronauts
21
            // Grow the running total so the next country pairs against this one too.
22
            seen += s;
23
        }
24
    }
25
    return answer;
26
}
27
 
28
private int find(int[] parent, int x) {
29
    while (parent[x] != x) {
30
        // Compress while climbing; the loop is stack-safe for deep groups.
31
        parent[x] = parent[parent[x]];        // path halving, iterative
32
        x = parent[x];
33
    }
34
    return x;
35
}
36
 
37
private void union(int[] parent, int[] rank, int[] size, int a, int b) {
38
    int ra = find(parent, a), rb = find(parent, b);
39
    if (ra == rb) return;
40
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
41
    parent[rb] = ra;
42
    size[ra] += size[rb];
43
    if (rank[ra] == rank[rb]) rank[ra]++;
44
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.44 lines

D · Why it works and complexityO(N + E·α(N)) timeO(N) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7N = 1, pairs = [] — One astronaut, no possible pair → C(1,2) = 0. answer = 0.Explore edge cases

Edge cases handled

N = 1, pairs = []One astronaut, no possible pair → C(1,2) = 0. answer = 0.
all astronauts same countryOne component of size N. seen stays 0 through the single country → answer 0; no cross pairs exist.
no pairs at allN singleton countries → answer = C(N,2); every pair is cross-country.

Pitfalls

Returning same-country pairs instead of their complement.
Accumulating in int — answer up to 5 × 10⁹ overflows; use long.
Counting size off non-root nodes — only the root holds the true component size.
Recursive find on a deep group — risks stack overflow; use the iterative loop.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long journeyToMoon(int n, int[][] pairs) { int[] parent = new int[n]; int[] rank = new int[n]; int[] size = new int[n]; for (int i = 0; i < n; i++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];        // path halving, iterative
        x = parent[x];
    }
    return x;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning same-country pairs

The question asks for pairs from DIFFERENT countries. Summing C(sᵢ,2) gives the forbidden same-country pairs — the exact opposite of the answer.

Explore the code comparison

Don't write this

return sum(s * (s - 1) // 2 for s in sizes)   # same-country pairs

Write this instead

total = n * (n - 1) // 2
return total - sum(s * (s - 1) // 2 for s in sizes)

32-bit overflow on C(N,2)

For N = 10⁵, n*(n-1)/2 ≈ 5 × 10⁹, far beyond int's 2.1 × 10⁹ ceiling. The product n*(n-1) overflows before the division.

Explore the code comparison

Don't write this

int total = n * (n - 1) / 2;          // n*(n-1) overflows int

Write this instead

long total = (long) n * (n - 1) / 2;  // promote before multiplying

Missing isolated astronauts

An astronaut never named in any pair forms a country of one and pairs with everyone else. Only iterating over astronauts that appear in pairs drops these singletons and undercounts.

Explore the code comparison

Don't write this

for a, b in pairs:        # only touches astronauts that appear in a pair
    union(a, b)
sizes = component_sizes_of_seen_nodes()

Write this instead

parent = list(range(n))   # every astronaut 0..n-1 starts as its own country
for a, b in pairs:
    union(a, b)
# sweep all n astronauts, including untouched singletons

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Component sizes via Union-Find, then complementary counting

Code pattern to memorize

sizes = component sizes from union-find
# complementary form
answer = N*(N-1)/2 - sum(s*(s-1)/2 for s in sizes)
# running-sum form (no big intermediate)
seen = 0; answer = 0
for s in sizes:
    answer += s * seen
    seen += s

Rules to remember

1Two astronauts in the same component are the same country — never a valid pair. Count its complement.
2Use long: with N up to 10⁵, C(N,2) is about 5 × 10⁹, well past 32-bit range.
3Every astronaut counts, including isolated ones — they are singleton components of size 1.
4The running-sum form answer += s × seen avoids forming the huge C(N,2) and is overflow-friendlier.
5Pick Union-Find for connectivity-only counting; you never need paths, just group sizes.

Use this pattern when

Count cross-group pairs when items split into disjoint groups
Connectivity defines the groups (a relation that is symmetric and transitive)
You need group **sizes**, not paths or distances
Complementary counting (total − unwanted) is simpler than counting wanted directly

Choose another pattern when

You need the actual partner pairs, not the count → enumerate, but that is O(N²)
Groups overlap or an item belongs to many → not disjoint sets
You need shortest distance between astronauts → BFS, not component sizing
Pairs must satisfy extra constraints beyond 'different country' → counting gets case-specific

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of Connected Components
The same Union-Find grouping, returning the component count instead of a pair tally.
Components in a Graph
Report smallest and largest component sizes — another read off the same size array.
Roads and Libraries
Per-component greedy cost instead of a pair count, again powered by component sizes.
Count of Pairs With Given Property
Coming soon
Generalized cross-group pair counting with the running-sum s × seen accumulation.

Same pattern

←

Find the Nearest Clone

Continue · Next problem

Roads and Libraries