Loading…

mediumGraphsSometimes asked

Roads and Libraries

Q: How do you solve Roads and Libraries using the DFS / BFS Component Sizing (Baseline) approach?

When to use it: Mention first as the most direct way to get component sizes — a flood fill over an adjacency list. It is just as correct as Union-Find; the cost formula is identical. The graph problem hidden inside this question is simply *component sizing*. Once you know how many cities sit in each connected group, the money question is pure arithmetic. **Why a flood fill gives the sizes.** Start at any unvisited city and walk every city reachable from it through roads, marking each visited and counting as you go. When the walk stalls, you have one full component and its size. Pick the next unvisited city and repeat. Every city is reached exactly once, so the sizes you collect partition all `n` cities. **Why the traversal must be iterative here.** With up to `10⁵` cities a recursive DFS can nest `10⁵` frames deep on a long chain of roads and overflow the call stack. Use an explicit stack (or a queue for BFS) so the depth lives in the heap, not the call stack. The order of visiting does not matter — DFS and BFS both produce the same component sizes. **Why the cost is per-component and additive.** A road can only ever join two cities that are already in the same component (that is what a road *does*). So no spending in one component can help another, and the global minimum is just the sum of each component's own minimum. Inside a component of size `s` you compare two complete plans: a library in all `s` cities, or a single library plus the `s − 1` roads that connect the rest to it. Time complexity: O(N + E). Space complexity: O(N + E).

Q: How do you solve Roads and Libraries using the Union-Find Component Sizing (Optimal) approach?

When to use it: The cleanest answer when you only need connectivity, not paths. Phrase it as 'union each road's endpoints, then read off component sizes from the roots'. Union-Find (a disjoint-set forest) is the tool when the *only* question about the graph is 'which things are connected'. It never materializes paths, so it sidesteps all traversal and the stack-depth worry entirely. **How the grouping works.** Each city starts as its own set. For every road `[u, v]` you `union` the two endpoints — merging their sets if they differ. After all roads are processed, two cities share a root exactly when a chain of roads connects them. The `size[]` array, carried on each root, then tells you how big each component is. **Why union by rank plus path compression matters.** A naïve `find` that walks parents to the root can degrade to `O(N)` on a skewed tree, making the whole run `O(N·E)`. Path compression flattens the tree during `find` (pointing nodes at their grandparent), and union by rank attaches the shorter tree under the taller one. Together they pin each operation at `O(α(N))`, which is at most 4 for any input you will ever see — effectively constant. **Why the find loop is iterative.** `find` climbs parent pointers in a `while` loop, never recursing. On `10⁵` cities that avoids any chance of a deep recursive call blowing the stack — the same defensive choice as the iterative DFS, applied to the set-find. **Reading the answer.** Sweep all `n` cities, find each city's root, and accumulate the count per root. Each distinct root is one component of some size `s`, and you add `min(s × c_lib, c_lib + (s − 1) × c_road)` for it. Sum across roots for the total. The `c_lib ≤ c_road` shortcut still applies — when libraries are cheaper, every component picks the `s × c_lib` branch and the total collapses to `n × c_lib`. Time complexity: O(E · α(N)). Space complexity: O(N).

Graphs · 27 of 34 · 12 min

The HackerLand government wants every citizen to have access to a library. There are n cities (numbered 1 to n) and a list of bidirectional roads that could be repaired, where roads[i] = [u, v] means a road can be repaired between city u and city v.

Building a library in a city costs c_lib. Repairing one road costs c_road. A city has access to a library if it contains one, or if it is connected through repaired roads to a city that contains one.

Return the minimum total cost to give every city access to a library.

In plain English

Each city must end up linked (directly or via roads) to at least one library. Roads only matter inside a group of cities that the road list connects. Within one such group you pay for exactly one library and then choose the cheaper of 'a library everywhere' versus 'one library plus enough roads to reach the rest'. Different groups never interact, so total cost is the sum of each group's own cheapest plan.

Examples

Example 1

Input: n = 3, c_lib = 2, c_road = 1, roads = [[1,2],[3,1],[2,3]]
Output: 4
Note: All 3 cities form one component. Roads are cheaper (1 < 2): one library (2) + (3−1) roads (2×1=2) = 4. Building 3 libraries would cost 6.

Example 2

Input: n = 6, c_lib = 2, c_road = 5, roads = [[1,3],[3,4],[2,4],[1,2],[2,3],[5,6]]
Output: 12
Note: Libraries are cheaper (2 ≤ 5), so ignore roads and build a library in every city: 6 × 2 = 12.

Example 3

Input: n = 5, c_lib = 6, c_road = 1, roads = [[1,2],[1,3],[1,4]]
Output: 15
Note: Component {1,2,3,4} size 4: min(4×6, 6 + 3×1) = min(24, 9) = 9. City 5 is alone: 6. Total 9 + 6 = 15.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ roads.length ≤ min(n·(n−1)/2, 10⁵)
1 ≤ c_lib, c_road ≤ 10⁵
Roads are bidirectional; the graph may be disconnected
The answer can exceed 32-bit range — use 64-bit

Clarifying questions4First question: Are the cities 1-indexed or 0-indexed?Explore questions

Q1.Are the cities 1-indexed or 0-indexed?
The HackerRank statement uses 1..n. Internally I will shift to 0-based for array-backed Union-Find and shift back only at the boundary.
Q2.Can the same road appear twice, or can there be self-loops?
Duplicate roads and self-loops are harmless — Union-Find ignores an edge whose endpoints already share a root, so no extra cost is added.
Q3.Must the whole map be connected at the end?
No. Each component is solved on its own; an isolated city just gets its own library.
Q4.Is it ever right to repair more than s − 1 roads in a component of size s?
Never. s − 1 roads already connect all s cities (a spanning tree). Any extra road only adds cost without improving access.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Group cities into connected components from the road list, then decide each component independently. Inside a component of size s you must place at least one library; the cheapest way to reach all s cities is either s libraries (s × c_lib) or one library plus s − 1 roads (c_lib + (s − 1) × c_road). Take the per-component minimum and sum. Union-Find finds the components in O(E · α(N)).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you see that the graph decomposes into independent connected components and that each component reduces to a tiny greedy choice, rather than reaching for an expensive shortest-path or MST routine.

Where candidates slip

Forgetting that every component still needs one library even when roads are cheaper, or using a 32-bit int for the total and overflowing on large inputs.

How to stand out

Call out the `c_lib ≤ c_road` shortcut immediately, derive 'span s cities with s − 1 roads' as a spanning tree, and explain why components are independent so the costs simply add.

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 Sizing (Baseline)	`O(N + E)`	`O(N + E)`	Mention first as the most direct way to get component sizes — a flood fill over an adjacency list. It is just as correct as Union-Find; the cost formula is identical.	Read
2	Union-Find Component Sizing (Optimal)Optimal	`O(E · α(N))`	`O(N)`	The cleanest answer when you only need connectivity, not paths. Phrase it as 'union each road's endpoints, then read off component sizes from the roots'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewComponent of size sc_lib ≤ c_road?YesNoExplore the full tree

Two components, priced independently

How to read it:Component {1,2,3,4} and the lone city 5. Each is solved on its own and the costs are added.

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 Sizing (Baseline)

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

Mention first as the most direct way to get component sizes — a flood fill over an adjacency list. It is just as correct as Union-Find; the cost formula is identical.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Strip away the cost question for a moment. What you really need from the graph is: how many cities are in each connected group?

2Hint 2Explore hint

Build an adjacency list, then walk every unvisited city, flood-filling its whole component and counting how many cities you touch.

3Hint 3Explore hint

For each component size s you collect, add min(s × c_lib, c_lib + (s − 1) × c_road) to the answer.

A · Core idea

The graph problem hidden inside this question is simply component sizing. Once you know how many cities sit in each connected group, the money question is pure arithmetic.

Why a flood fill gives the sizes. Start at any unvisited city and walk every city reachable from it through roads, marking each visited and counting as you go. When the walk stalls, you have one full component and its size. Pick the next unvisited city and repeat. Every city is reached exactly once, so the sizes you collect partition all n cities.

Why the traversal must be iterative here. With up to 10⁵ cities a recursive DFS can nest 10⁵ frames deep on a long chain of roads and overflow the call stack. Use an explicit stack (or a queue for BFS) so the depth lives in the heap, not the call stack. The order of visiting does not matter — DFS and BFS both produce the same component sizes.

Why the cost is per-component and additive. A road can only ever join two cities that are already in the same component (that is what a road does). So no spending in one component can help another, and the global minimum is just the sum of each component's own minimum. Inside a component of size s you compare two complete plans: a library in all s cities, or a single library plus the s − 1 roads that connect the rest to it.

B · Visual dry run

Interactive dry run

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

n = 5, c_lib = 6, c_road = 1, roads = [[1,2],[1,3],[1,4]]

Interactive diagram

Flood fill discovering one component

start city 1

Active call / nodeSupporting contextReturned stateNot active

Starting at city 1, the iterative DFS reaches 2, 3, 4 — size 4.

Final result15

C · Code with teaching comments

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

solution.javaJava

DFS / BFS Component Sizing (Baseline) — reference

3 teaching notes

1
public long roadsAndLibraries(int n, int cLib, int cRoad, int[][] roads) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
4
    for (int[] r : roads) {
5
        adj.get(r[0]).add(r[1]);
6
        adj.get(r[1]).add(r[0]);
7
    }
8
    boolean[] visited = new boolean[n + 1];
9
    long total = 0;
10
    for (int start = 1; start <= n; start++) {
11
        if (visited[start]) continue;
12
        int size = 0;
13
        Deque<Integer> stack = new ArrayDeque<>();
14
        stack.push(start);
15
        visited[start] = true;
16
        // An explicit stack keeps depth on the heap — a recursive DFS would risk
17
        // overflow at 10⁵ cities.
18
        while (!stack.isEmpty()) {          // iterative DFS, no stack overflow
19
            int u = stack.pop();
20
            size++;
21
            for (int v : adj.get(u)) {
22
                if (!visited[v]) {
23
                    visited[v] = true;
24
                    stack.push(v);
25
                }
26
            }
27
        }
28
        total += Math.min((long) size * cLib,
29
                          (long) cLib + (long) (size - 1) * cRoad);
30
    }
31
    return total;
32
}

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

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

The whole problem is 'find component sizes, then apply a fixed two-line formula'. Recognizing that the cost decomposes per component is the real insight — the traversal is just bookkeeping.

ComplexityO(N + E) time, O(N + E) space — Building the adjacency list is O(N + E). Each vertex and edge is visited once during the traversal, so the flood fill is O(N + E). The cost arithmetic per component is O(1).

E · Edge cases and pitfalls3Recursive DFS on a 10⁵-city chain — stack overflow. Use an explicit stack or BFS.Explore edge cases

Pitfalls

Recursive DFS on a 10⁵-city chain — stack overflow. Use an explicit stack or BFS.
Adding only one direction of each road — splits a component in two and overprices it.
Computing size × c_lib in 32-bit int — overflows around 2×10⁹.

03.2

Approach 2 of 2 · Optimal

Union-Find Component Sizing (Optimal)

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

The cleanest answer when you only need connectivity, not paths. Phrase it as 'union each road's endpoints, then read off component sizes from the roots'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You never need the actual roads after grouping — only which cities ended up together. What structure answers 'are these two in the same group?' in near-constant time?

2Hint 2Explore hint

Union-Find: union the two endpoints of every road, with path compression and union by rank. After processing all roads, the size of each root's set is its component size.

3Hint 3Explore hint

Walk every city, find its root, and tally how many cities map to each root. Then apply min(s × c_lib, c_lib + (s − 1) × c_road) per root.

A · Core idea

Union-Find (a disjoint-set forest) is the tool when the only question about the graph is 'which things are connected'. It never materializes paths, so it sidesteps all traversal and the stack-depth worry entirely.

How the grouping works. Each city starts as its own set. For every road [u, v] you union the two endpoints — merging their sets if they differ. After all roads are processed, two cities share a root exactly when a chain of roads connects them. The size[] array, carried on each root, then tells you how big each component is.

Why union by rank plus path compression matters. A naïve find that walks parents to the root can degrade to O(N) on a skewed tree, making the whole run O(N·E). Path compression flattens the tree during find (pointing nodes at their grandparent), and union by rank attaches the shorter tree under the taller one. Together they pin each operation at O(α(N)), which is at most 4 for any input you will ever see — effectively constant.

Why the find loop is iterative. find climbs parent pointers in a while loop, never recursing. On 10⁵ cities that avoids any chance of a deep recursive call blowing the stack — the same defensive choice as the iterative DFS, applied to the set-find.

Reading the answer. Sweep all n cities, find each city's root, and accumulate the count per root. Each distinct root is one component of some size s, and you add min(s × c_lib, c_lib + (s − 1) × c_road) for it. Sum across roots for the total. The c_lib ≤ c_road shortcut still applies — when libraries are cheaper, every component picks the s × c_lib branch and the total collapses to n × c_lib.

B · Visual dry run

Interactive dry run

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

n = 6, c_lib = 2, c_road = 5, roads = [[1,3],[3,4],[2,4],[1,2],[2,3],[5,6]]

Interactive diagram

Disjoint-set forest after all unions

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

Active call / nodeSupporting contextReturned stateNot active

Roads merged {1,2,3,4} under one root and {5,6} under another — two components of size 4 and 2.

Final result12

C · Code with teaching comments

solution.javaJava

Union-Find Component Sizing (Optimal) — optimal

4 teaching notes

1
public long roadsAndLibraries(int n, int cLib, int cRoad, int[][] roads) {
2
    if (cLib <= cRoad) {
3
        return (long) n * cLib;          // libraries never lose — skip roads entirely
4
    }
5
    int[] parent = new int[n + 1];
6
    int[] rank = new int[n + 1];
7
    int[] size = new int[n + 1];
8
    for (int i = 1; i <= n; i++) {
9
        parent[i] = i;
10
        size[i] = 1;
11
    }
12
    for (int[] r : roads) {
13
        union(parent, rank, size, r[0], r[1]);
14
    }
15
    long total = 0;
16
    for (int i = 1; i <= n; i++) {
17
        // A node equal to its own parent is a root, marking exactly one component to
18
        // price.
19
        if (find(parent, i) == i) {       // i is a root → one component
20
            int s = size[i];
21
            // Roads are the cheaper branch here: one library plus the s − 1 roads that
22
            // span the component.
23
            total += (long) cLib + (long) (s - 1) * cRoad;
24
        }
25
    }
26
    return total;
27
}
28
 
29
private int find(int[] parent, int x) {
30
    while (parent[x] != x) {
31
        // Compress the path while climbing; the while loop keeps it stack-safe at 10⁵
32
        // nodes.
33
        parent[x] = parent[parent[x]];   // path halving, iterative
34
        x = parent[x];
35
    }
36
    return x;
37
}
38
 
39
private void union(int[] parent, int[] rank, int[] size, int a, int b) {
40
    int ra = find(parent, a), rb = find(parent, b);
41
    if (ra == rb) return;
42
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
43
    parent[rb] = ra;
44
    size[ra] += size[rb];
45
    if (rank[ra] == rank[rb]) rank[ra]++;
46
}

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

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

Union-Find is the reflex whenever a problem is purely about connectivity with no need for distances or paths. It turns the graph into a near-constant-time 'same group?' oracle, leaving only the O(1)-per-component cost formula to finish the job.

ComplexityO(E · α(N)) time, O(N) space — Each union and find is O(α(N)) — the inverse Ackermann function, effectively constant. E roads give O(E · α(N)); the final sweep over N cities to read sizes is O(N · α(N)). Space is O(N) for the parent and size arrays.

E · Edge cases and pitfalls7n = 1, c_lib = 5, c_road = 3, roads = [] — One component of size 1: min(5, 5 + 0) = 5. A lone city always just buys a library.Explore edge cases

Edge cases handled

n = 1, c_lib = 5, c_road = 3, roads = []One component of size 1: min(5, 5 + 0) = 5. A lone city always just buys a library.
roads = [[1,2],[1,2]] (duplicate)Second union finds equal roots → no-op. Duplicates and self-loops never add cost.
c_lib = c_roadmin(s·c, c + (s−1)·c) = s·c either way — the shortcut returns n·c_lib, still correct.

Pitfalls

Dropping the per-component library — a component of size s with only roads has no library to reach.
Recursive find on a long chain — risks stack overflow; the iterative while loop avoids it.
Accumulating the total in 32-bit int — n × c_lib can reach 10¹⁰, well past int range.
Counting size off non-root nodes — only the root carries the correct component size.

Practice

Try the solution yourself

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

Editable code previewpublic long roadsAndLibraries(int n, int cLib, int cRoad, int[][] roads) { if (cLib <= cRoad) { return (long) n * cLib; // libraries never lose — skip roads entirely } int[] parent = new int[n + 1];Explore the playground

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

public long roadsAndLibraries(int n, int cLib, int cRoad, int[][] roads) {
    if (cLib <= cRoad) {
        return (long) n * cLib;          // libraries never lose — skip roads entirely
    }
    int[] parent = new int[n + 1];
    int[] rank = new int[n + 1];
    int[] size = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    for (int[] r : roads) {
        union(parent, rank, size, r[0], r[1]);
    }
    long total = 0;
    for (int i = 1; i <= n; i++) {
        if (find(parent, i) == i) {       // i is a root → one component
            int s = size[i];
            total += (long) cLib + (long) (s - 1) * cRoad;
        }
    }
    return total;
}

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.

Skipping the mandatory per-component library

When roads are cheaper, candidates sometimes price a component as (s − 1) × c_road and forget the one library that makes the roads worth anything. Without a library, a connected component still has zero access.

Explore the code comparison

Don't write this

# roads cheaper, but no library bought
total += (size - 1) * c_road

Write this instead

# one library anchors the component, roads reach the rest
total += c_lib + (size - 1) * c_road

32-bit overflow on the total

With n up to 10⁵ and costs up to 10⁵, a single component can cost on the order of 10¹⁰, which silently wraps around in a 32-bit int and yields a negative or tiny answer.

Explore the code comparison

Don't write this

int total = 0;
total += size * cLib;          // size * cLib overflows int

Write this instead

long total = 0;
total += (long) size * cLib;   // promote before multiplying

Recursive find / DFS blowing the stack

A path of 10⁵ cities forms a chain that deep. Recursive find or DFS nests one frame per node and overflows the call stack; an explicit loop keeps the depth in the heap.

Explore the code comparison

Don't write this

def find(x):
    if parent[x] == x:
        return x
    return find(parent[x])     # recursion depth = chain length

Write this instead

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Connected components + per-component greedy choice

Code pattern to memorize

components = union-find over roads
for each component of size s:
    cost += min(s * c_lib,                      # a library in every city
                c_lib + (s - 1) * c_road)       # one library, span with roads
answer = sum of per-component costs

Rules to remember

1Every component needs at least one library — a city with no library can never reach one through roads alone.
2If c_lib ≤ c_road, libraries are never worse than roads — the answer is just n * c_lib. State this special case first.
3Spanning a component of s cities needs exactly s − 1 roads (a spanning tree); extra roads are wasted money.
4Decide each component independently — roads only connect cities already in the same component, so components never share cost.
5Use long for the running total: n up to 10⁵ times costs up to 10⁵ overflows 32-bit int.

Use this pattern when

Cost is split between a 'node cost' and an 'edge cost' and you must cover every node
The graph breaks into independent pieces you can price separately
You only need connectivity (reach a facility), not actual shortest distances
The decision per group is a simple two-way greedy comparison

Choose another pattern when

You need the actual shortest path between two cities → BFS / Dijkstra, not components
Edges carry differing weights you must minimize over → that is an MST (Kruskal/Prim), not this flat comparison
You must keep the graph connected as a whole → spanning-tree problem, not per-component
Libraries have per-city differing costs → this uniform-cost greedy no longer applies

Interview takeaway

When a problem splits cleanly into independent groups, price each group on its own and add the results. Here the only graph work is 'which cities are connected', which Union-Find answers in near-constant time per edge — the rest is a one-line cost comparison.

Continue

Transfer the pattern to another problem

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

Transferable patternConnected Components + Independent Per-Group Greedy. Recognize it when a graph splits into pieces you can price separately and each piece reduces to a small comparison. Union-Find supplies the component sizes in near-constant time per edge; the same skeleton appears in Components in a Graph, Number of Provinces, and Journey to the Moon.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Journey to the Moon

Continue · Next problem

Snakes and Ladders: The Quickest Way Up

mediumGraphsSometimes asked

Roads and Libraries

Graphs · 27 of 34 · 12 min

Return the minimum total cost to give every city access to a library.

In plain English

Examples

Example 1

Input: n = 3, c_lib = 2, c_road = 1, roads = [[1,2],[3,1],[2,3]]
Output: 4
Note: All 3 cities form one component. Roads are cheaper (1 < 2): one library (2) + (3−1) roads (2×1=2) = 4. Building 3 libraries would cost 6.

Example 2

Input: n = 6, c_lib = 2, c_road = 5, roads = [[1,3],[3,4],[2,4],[1,2],[2,3],[5,6]]
Output: 12
Note: Libraries are cheaper (2 ≤ 5), so ignore roads and build a library in every city: 6 × 2 = 12.

Example 3

Input: n = 5, c_lib = 6, c_road = 1, roads = [[1,2],[1,3],[1,4]]
Output: 15
Note: Component {1,2,3,4} size 4: min(4×6, 6 + 3×1) = min(24, 9) = 9. City 5 is alone: 6. Total 9 + 6 = 15.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ roads.length ≤ min(n·(n−1)/2, 10⁵)
1 ≤ c_lib, c_road ≤ 10⁵
Roads are bidirectional; the graph may be disconnected
The answer can exceed 32-bit range — use 64-bit

Clarifying questions4First question: Are the cities 1-indexed or 0-indexed?Explore questions

Q1.Are the cities 1-indexed or 0-indexed?
The HackerRank statement uses 1..n. Internally I will shift to 0-based for array-backed Union-Find and shift back only at the boundary.
Q2.Can the same road appear twice, or can there be self-loops?
Duplicate roads and self-loops are harmless — Union-Find ignores an edge whose endpoints already share a root, so no extra cost is added.
Q3.Must the whole map be connected at the end?
No. Each component is solved on its own; an isolated city just gets its own library.
Q4.Is it ever right to repair more than s − 1 roads in a component of size s?
Never. s − 1 roads already connect all s cities (a spanning tree). Any extra road only adds cost without improving access.

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

Where candidates slip

Forgetting that every component still needs one library even when roads are cheaper, or using a 32-bit int for the total and overflowing on large inputs.

How to stand out

Call out the `c_lib ≤ c_road` shortcut immediately, derive 'span s cities with s − 1 roads' as a spanning tree, and explain why components are independent so the costs simply add.

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 Sizing (Baseline)	`O(N + E)`	`O(N + E)`	Mention first as the most direct way to get component sizes — a flood fill over an adjacency list. It is just as correct as Union-Find; the cost formula is identical.	Read
2	Union-Find Component Sizing (Optimal)Optimal	`O(E · α(N))`	`O(N)`	The cleanest answer when you only need connectivity, not paths. Phrase it as 'union each road's endpoints, then read off component sizes from the roots'.	Read

Two components, priced independently

How to read it:Component {1,2,3,4} and the lone city 5. Each is solved on its own and the costs are added.

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 Sizing (Baseline)

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

Mention first as the most direct way to get component sizes — a flood fill over an adjacency list. It is just as correct as Union-Find; the cost formula is identical.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Strip away the cost question for a moment. What you really need from the graph is: how many cities are in each connected group?

2Hint 2Explore hint

Build an adjacency list, then walk every unvisited city, flood-filling its whole component and counting how many cities you touch.

3Hint 3Explore hint

For each component size s you collect, add min(s × c_lib, c_lib + (s − 1) × c_road) to the answer.

A · Core idea

The graph problem hidden inside this question is simply component sizing. Once you know how many cities sit in each connected group, the money question is pure arithmetic.

B · Visual dry run

Interactive dry run

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

n = 5, c_lib = 6, c_road = 1, roads = [[1,2],[1,3],[1,4]]

Interactive diagram

Flood fill discovering one component

start city 1

Active call / nodeSupporting contextReturned stateNot active

Starting at city 1, the iterative DFS reaches 2, 3, 4 — size 4.

Final result15

C · Code with teaching comments

solution.javaJava

DFS / BFS Component Sizing (Baseline) — reference

3 teaching notes

1
public long roadsAndLibraries(int n, int cLib, int cRoad, int[][] roads) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
4
    for (int[] r : roads) {
5
        adj.get(r[0]).add(r[1]);
6
        adj.get(r[1]).add(r[0]);
7
    }
8
    boolean[] visited = new boolean[n + 1];
9
    long total = 0;
10
    for (int start = 1; start <= n; start++) {
11
        if (visited[start]) continue;
12
        int size = 0;
13
        Deque<Integer> stack = new ArrayDeque<>();
14
        stack.push(start);
15
        visited[start] = true;
16
        // An explicit stack keeps depth on the heap — a recursive DFS would risk
17
        // overflow at 10⁵ cities.
18
        while (!stack.isEmpty()) {          // iterative DFS, no stack overflow
19
            int u = stack.pop();
20
            size++;
21
            for (int v : adj.get(u)) {
22
                if (!visited[v]) {
23
                    visited[v] = true;
24
                    stack.push(v);
25
                }
26
            }
27
        }
28
        total += Math.min((long) size * cLib,
29
                          (long) cLib + (long) (size - 1) * cRoad);
30
    }
31
    return total;
32
}

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

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

The whole problem is 'find component sizes, then apply a fixed two-line formula'. Recognizing that the cost decomposes per component is the real insight — the traversal is just bookkeeping.

E · Edge cases and pitfalls3Recursive DFS on a 10⁵-city chain — stack overflow. Use an explicit stack or BFS.Explore edge cases

Pitfalls

Recursive DFS on a 10⁵-city chain — stack overflow. Use an explicit stack or BFS.
Adding only one direction of each road — splits a component in two and overprices it.
Computing size × c_lib in 32-bit int — overflows around 2×10⁹.

03.2

Approach 2 of 2 · Optimal

Union-Find Component Sizing (Optimal)

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

The cleanest answer when you only need connectivity, not paths. Phrase it as 'union each road's endpoints, then read off component sizes from the roots'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You never need the actual roads after grouping — only which cities ended up together. What structure answers 'are these two in the same group?' in near-constant time?

2Hint 2Explore hint

Union-Find: union the two endpoints of every road, with path compression and union by rank. After processing all roads, the size of each root's set is its component size.

3Hint 3Explore hint

Walk every city, find its root, and tally how many cities map to each root. Then apply min(s × c_lib, c_lib + (s − 1) × c_road) per root.

A · Core idea

B · Visual dry run

Interactive dry run

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

n = 6, c_lib = 2, c_road = 5, roads = [[1,3],[3,4],[2,4],[1,2],[2,3],[5,6]]

Interactive diagram

Disjoint-set forest after all unions

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

Active call / nodeSupporting contextReturned stateNot active

Roads merged {1,2,3,4} under one root and {5,6} under another — two components of size 4 and 2.

Final result12

C · Code with teaching comments

solution.javaJava

Union-Find Component Sizing (Optimal) — optimal

4 teaching notes

1
public long roadsAndLibraries(int n, int cLib, int cRoad, int[][] roads) {
2
    if (cLib <= cRoad) {
3
        return (long) n * cLib;          // libraries never lose — skip roads entirely
4
    }
5
    int[] parent = new int[n + 1];
6
    int[] rank = new int[n + 1];
7
    int[] size = new int[n + 1];
8
    for (int i = 1; i <= n; i++) {
9
        parent[i] = i;
10
        size[i] = 1;
11
    }
12
    for (int[] r : roads) {
13
        union(parent, rank, size, r[0], r[1]);
14
    }
15
    long total = 0;
16
    for (int i = 1; i <= n; i++) {
17
        // A node equal to its own parent is a root, marking exactly one component to
18
        // price.
19
        if (find(parent, i) == i) {       // i is a root → one component
20
            int s = size[i];
21
            // Roads are the cheaper branch here: one library plus the s − 1 roads that
22
            // span the component.
23
            total += (long) cLib + (long) (s - 1) * cRoad;
24
        }
25
    }
26
    return total;
27
}
28
 
29
private int find(int[] parent, int x) {
30
    while (parent[x] != x) {
31
        // Compress the path while climbing; the while loop keeps it stack-safe at 10⁵
32
        // nodes.
33
        parent[x] = parent[parent[x]];   // path halving, iterative
34
        x = parent[x];
35
    }
36
    return x;
37
}
38
 
39
private void union(int[] parent, int[] rank, int[] size, int a, int b) {
40
    int ra = find(parent, a), rb = find(parent, b);
41
    if (ra == rb) return;
42
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
43
    parent[rb] = ra;
44
    size[ra] += size[rb];
45
    if (rank[ra] == rank[rb]) rank[ra]++;
46
}

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

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

E · Edge cases and pitfalls7n = 1, c_lib = 5, c_road = 3, roads = [] — One component of size 1: min(5, 5 + 0) = 5. A lone city always just buys a library.Explore edge cases

Edge cases handled

n = 1, c_lib = 5, c_road = 3, roads = []One component of size 1: min(5, 5 + 0) = 5. A lone city always just buys a library.
roads = [[1,2],[1,2]] (duplicate)Second union finds equal roots → no-op. Duplicates and self-loops never add cost.
c_lib = c_roadmin(s·c, c + (s−1)·c) = s·c either way — the shortcut returns n·c_lib, still correct.

Pitfalls

Dropping the per-component library — a component of size s with only roads has no library to reach.
Recursive find on a long chain — risks stack overflow; the iterative while loop avoids it.
Accumulating the total in 32-bit int — n × c_lib can reach 10¹⁰, well past int range.
Counting size off non-root nodes — only the root carries the correct component size.

Practice

Try the solution yourself

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

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.

Skipping the mandatory per-component library

Explore the code comparison

Don't write this

# roads cheaper, but no library bought
total += (size - 1) * c_road

Write this instead

# one library anchors the component, roads reach the rest
total += c_lib + (size - 1) * c_road

32-bit overflow on the total

With n up to 10⁵ and costs up to 10⁵, a single component can cost on the order of 10¹⁰, which silently wraps around in a 32-bit int and yields a negative or tiny answer.

Explore the code comparison

Don't write this

int total = 0;
total += size * cLib;          // size * cLib overflows int

Write this instead

long total = 0;
total += (long) size * cLib;   // promote before multiplying

Recursive find / DFS blowing the stack

A path of 10⁵ cities forms a chain that deep. Recursive find or DFS nests one frame per node and overflows the call stack; an explicit loop keeps the depth in the heap.

Explore the code comparison

Don't write this

def find(x):
    if parent[x] == x:
        return x
    return find(parent[x])     # recursion depth = chain length

Write this instead

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Connected components + per-component greedy choice

Code pattern to memorize

components = union-find over roads
for each component of size s:
    cost += min(s * c_lib,                      # a library in every city
                c_lib + (s - 1) * c_road)       # one library, span with roads
answer = sum of per-component costs

Rules to remember

1Every component needs at least one library — a city with no library can never reach one through roads alone.
2If c_lib ≤ c_road, libraries are never worse than roads — the answer is just n * c_lib. State this special case first.
3Spanning a component of s cities needs exactly s − 1 roads (a spanning tree); extra roads are wasted money.
4Decide each component independently — roads only connect cities already in the same component, so components never share cost.
5Use long for the running total: n up to 10⁵ times costs up to 10⁵ overflows 32-bit int.

Use this pattern when

Cost is split between a 'node cost' and an 'edge cost' and you must cover every node
The graph breaks into independent pieces you can price separately
You only need connectivity (reach a facility), not actual shortest distances
The decision per group is a simple two-way greedy comparison

Choose another pattern when

You need the actual shortest path between two cities → BFS / Dijkstra, not components
Edges carry differing weights you must minimize over → that is an MST (Kruskal/Prim), not this flat comparison
You must keep the graph connected as a whole → spanning-tree problem, not per-component
Libraries have per-city differing costs → this uniform-cost greedy no longer applies

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

Same pattern

←

Journey to the Moon

Continue · Next problem

Snakes and Ladders: The Quickest Way Up