Loading…

mediumGraphsSometimes asked

Components in a Graph

Q: How do you solve Components in a Graph using the DFS / BFS Flood Fill (Baseline) approach?

When to use it: A natural first take: build an adjacency list, flood-fill each unvisited node to measure its component, and track the min and max sizes. Correct and intuitive. If the only quantity you need is each component's size, a flood fill delivers it directly. **Why flood fill works.** Start at any unvisited node and walk every node reachable through edges, marking visited and counting. When the walk stalls you have one full component and its exact size. Move to the next unvisited node and repeat. Each node is counted once, so the sizes partition every node that has an edge. **Why iterate over only the nodes in edges.** Untouched labels are isolated and excluded by the problem, so it is cleanest to seed flood fills from nodes that actually appear in an edge (or to skip any component of size 1 when aggregating). **Why the traversal must be iterative.** With up to `3 × 10⁴` labels and `10⁵` edges, a component can be a long chain. A recursive DFS would nest one frame per node and risk a stack overflow, so use an explicit stack or a BFS queue. Order does not affect the sizes. **Aggregating extremes.** Keep `smallest` (seeded to infinity) and `largest` (seeded to 0). For each component of size `s ≥ 2`, update both. Seeding `smallest` to infinity — not 0 — is what lets the first real component set it. Time complexity: O(V + E). Space complexity: O(V + E).

Q: How do you solve Components in a Graph using the Union-Find with Size Tracking (Optimal) approach?

When to use it: The cleanest answer for a flat edge list. Union each edge, carry size on each root, then sweep roots for the smallest and largest. Union-Find is the natural fit when edges arrive as a list and you only care about group sizes. **Building components.** Every label starts in its own set. For each edge `[u, v]`, `union(u, v)`: if their roots differ, attach one tree under the other and add the smaller component's size onto the surviving root. After all edges, two labels share a root exactly when an edge-path connects them, and each root's `size` is its component size. **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 beneath the taller one keep each operation at `O(α(N))` — at most about 4 for any realistic input. The `find` loop is a `while`, never recursive, so even a long chain of merges cannot overflow the stack. **Why size lives on the root.** When two sets merge, only the surviving root's `size` is updated. A non-root keeps whatever stale value it had before being absorbed, so you must read `size` only after confirming `find(x) == x`. Reading it at a non-root is the classic bug. **Aggregating.** Sweep all labels; for each that is its own root with `size ≥ 2`, update `smallest` (seeded to infinity) and `largest` (seeded to 0). Because every label in an edge sits in a component of size ≥ 2, the filter mainly guards against any label you might have allocated but never connected. The bipartite labeling never enters the logic — `union` treats left and right labels identically. Time complexity: O(E · α(N)). Space complexity: O(N).

Graphs · 22 of 34 · 11 min

There are 2 × N nodes in an undirected graph, labeled 1 to 2N. Each edge connects a node from the left set (1..N) to a node from the right set (N+1..2N). You are given a list of edges.

Return two values: the size of the smallest connected component and the size of the largest connected component, considering only components that contain at least two nodes.

In plain English

Every edge ties a left node to a right node, so any node that appears in an edge belongs to a component of size at least two. Nodes that never appear in any edge are alone and excluded. The task is purely about connectivity sizes: merge endpoints into groups, measure each group, and report the extremes. The left/right (bipartite) split is a labeling detail — connectivity merging ignores it entirely.

Examples

Example 1

Input: edges = [[1,6],[2,7],[3,8],[4,9],[2,6]]
Output: 2 4
Note: Edge 2–6 links the {1,6} and {2,7} groups into {1,2,6,7} (size 4). {3,8} and {4,9} stay size 2. Smallest 2, largest 4.

Example 2

Input: edges = [[1,5],[1,6],[2,4]]
Output: 2 3
Note: {1,5,6} has size 3, {2,4} has size 2. Smallest 2, largest 3.

Example 3

Input: edges = [[1,2]]
Output: 2 2
Note: A single component of size 2 — smallest and largest coincide.

Constraints

1 ≤ N ≤ 1.5 × 10⁴ (so up to 3 × 10⁴ node labels)
1 ≤ edges.length ≤ 10⁵
Each edge's left endpoint is in 1..N, right endpoint in N+1..2N
The graph is undirected; isolated nodes (in no edge) are ignored
At least one edge exists, so at least one component of size ≥ 2 exists

Clarifying questions4First question: Do isolated nodes count as size-1 components?Explore questions

Q1.Do isolated nodes count as size-1 components?
No. The problem only considers components with at least two nodes, and every node in an edge is already in one. Untouched labels are ignored.
Q2.Does the bipartite structure matter to the algorithm?
Not for sizing. Union-Find merges whatever labels an edge connects; the left/right split is irrelevant to connected components.
Q3.Can the same edge appear twice?
Yes, and it is harmless — a union whose endpoints already share a root does nothing.
Q4.Could there be a single giant component?
Yes — then smallest and largest are equal. Seed smallest to infinity so a lone component still sets both.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Group the nodes that appear in edges into connected components and report the smallest and largest component sizes (only components with at least two nodes count). Union each edge's endpoints with Union-Find, carry a size on every root, then sweep the roots for the min and max size. O(E · α(N)).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for Union-Find with size tracking on a connectivity-only question, read sizes only at roots, and correctly aggregate the min and max across components.

Where candidates slip

Reading the size array at a non-root node (stale value), counting isolated nodes that should be excluded, or initializing 'smallest' to 0 so it never updates.

How to stand out

Maintain size on merge, sweep only roots, seed smallest to +infinity, and note that the bipartite labeling is irrelevant to the merging — it is just an undirected graph.

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 Flood Fill (Baseline)	`O(V + E)`	`O(V + E)`	A natural first take: build an adjacency list, flood-fill each unvisited node to measure its component, and track the min and max sizes. Correct and intuitive.	Read
2	Union-Find with Size Tracking (Optimal)Optimal	`O(E · α(N))`	`O(N)`	The cleanest answer for a flat edge list. Union each edge, carry size on each root, then sweep roots for the smallest and largest.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewConnected components?Need paths or just sizes?PathsSizes onlyExplore the full tree

Three components of sizes 4, 2, 2

How to read it:Edge 2–6 fuses two pairs into a size-4 component; the others stay at size 2.

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 Flood Fill (Baseline)

TimeO(V + E)SpaceO(V + E)

A natural first take: build an adjacency list, flood-fill each unvisited node to measure its component, and track the min and max sizes. Correct and intuitive.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What do you need per component? Just its node count. How do you count every node reachable from a start?

2Hint 2Explore hint

Build an adjacency list, then walk each unvisited node, flood-filling its whole component and counting how many nodes it touches.

3Hint 3Explore hint

Track the smallest and largest counts among components with size ≥ 2 as you discover them.

A · Core idea

If the only quantity you need is each component's size, a flood fill delivers it directly.

Why flood fill works. Start at any unvisited node and walk every node reachable through edges, marking visited and counting. When the walk stalls you have one full component and its exact size. Move to the next unvisited node and repeat. Each node is counted once, so the sizes partition every node that has an edge.

Why iterate over only the nodes in edges. Untouched labels are isolated and excluded by the problem, so it is cleanest to seed flood fills from nodes that actually appear in an edge (or to skip any component of size 1 when aggregating).

Why the traversal must be iterative. With up to 3 × 10⁴ labels and 10⁵ edges, a component can be a long chain. A recursive DFS would nest one frame per node and risk a stack overflow, so use an explicit stack or a BFS queue. Order does not affect the sizes.

Aggregating extremes. Keep smallest (seeded to infinity) and largest (seeded to 0). For each component of size s ≥ 2, update both. Seeding smallest to infinity — not 0 — is what lets the first real component set it.

B · Visual dry run

Interactive dry run

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

edges = [[1,5],[1,6],[2,4]]

Interactive diagram

Flood fill measuring a component

flood from 1

Active call / nodeSupporting contextReturned stateNot active

From node 1 the walk reaches 5 and 6 — size 3.

Final result2 3

C · Code with teaching comments

Reference implementation previewpublic int[] componentSizes(int totalNodes, int[][] edges) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i <= totalNodes; i++) adj.add(new ArrayList<>()); boolean[] inEdge = new boolean[totalNodes + 1]; for (int[] e : edges) {Explore the full code

solution.javaJava

DFS / BFS Flood Fill (Baseline) — reference

3 teaching notes

1
public int[] componentSizes(int totalNodes, int[][] edges) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i <= totalNodes; i++) adj.add(new ArrayList<>());
4
    boolean[] inEdge = new boolean[totalNodes + 1];
5
    for (int[] e : edges) {
6
        adj.get(e[0]).add(e[1]);
7
        adj.get(e[1]).add(e[0]);
8
        inEdge[e[0]] = true;
9
        inEdge[e[1]] = true;
10
    }
11
    boolean[] visited = new boolean[totalNodes + 1];
12
    int smallest = Integer.MAX_VALUE, largest = 0;
13
    for (int start = 1; start <= totalNodes; start++) {
14
        if (!inEdge[start] || visited[start]) continue;
15
        int size = 0;
16
        Deque<Integer> stack = new ArrayDeque<>();
17
        stack.push(start);
18
        visited[start] = true;
19
        // Explicit stack keeps depth on the heap — safe for long-chain components.
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
        // Only components with at least two nodes count toward the answer.
31
        if (size >= 2) {
32
            smallest = Math.min(smallest, size);
33
            largest = Math.max(largest, size);
34
        }
35
    }
36
    return new int[]{smallest, largest};
37
}

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

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

The problem reduces to component sizes; a flood fill produces them in one linear pass. The only subtlety is aggregating correctly — seed the minimum to infinity so it can actually shrink.

ComplexityO(V + E) time, O(V + E) space — Building the adjacency list is O(V + E). Each node and edge is visited once during the flood fills → O(V + E). Tracking min/max is O(1) per component.

E · Edge cases and pitfalls3Recursive DFS on a long chain — stack overflow.Explore edge cases

Pitfalls

Recursive DFS on a long chain — stack overflow.
Seeding smallest to 0 — it can never decrease below 0, so it never updates.
Counting isolated nodes as size-1 components when the problem excludes them.

03.2

Approach 2 of 2 · Optimal

Union-Find with Size Tracking (Optimal)

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

The cleanest answer for a flat edge list. Union each edge, carry size on each root, then sweep roots for the smallest and largest.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You only need sizes, never paths. What structure merges groups and tracks their sizes in near-constant time per edge?

2Hint 2Explore hint

Union-Find: union each edge's endpoints with path compression and union by rank, and add the merged sizes onto the surviving root.

3Hint 3Explore hint

After all unions, scan the labels; for each label that is its own root, its size is its component size. Take the min and max over roots of size ≥ 2.

A · Core idea

Union-Find is the natural fit when edges arrive as a list and you only care about group sizes.

Building components. Every label starts in its own set. For each edge [u, v], union(u, v): if their roots differ, attach one tree under the other and add the smaller component's size onto the surviving root. After all edges, two labels share a root exactly when an edge-path connects them, and each root's size is its component size.

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 beneath the taller one keep each operation at O(α(N)) — at most about 4 for any realistic input. The find loop is a while, never recursive, so even a long chain of merges cannot overflow the stack.

Why size lives on the root. When two sets merge, only the surviving root's size is updated. A non-root keeps whatever stale value it had before being absorbed, so you must read size only after confirming find(x) == x. Reading it at a non-root is the classic bug.

Aggregating. Sweep all labels; for each that is its own root with size ≥ 2, update smallest (seeded to infinity) and largest (seeded to 0). Because every label in an edge sits in a component of size ≥ 2, the filter mainly guards against any label you might have allocated but never connected. The bipartite labeling never enters the logic — union treats left and right labels identically.

B · Visual dry run

Interactive dry run

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

edges = [[1,6],[2,7],[3,8],[4,9],[2,6]]

Interactive diagram

Disjoint-set forest after all unions

union 1-6, 2-7, 3-8, 4-9

Active call / nodeSupporting contextReturned stateNot active

Root of the size-4 set holds size 4; the two size-2 sets hold 2 each.

Final result2 4

C · Code with teaching comments

solution.javaJava

Union-Find with Size Tracking (Optimal) — optimal

3 teaching notes

1
public int[] componentSizes(int totalNodes, int[][] edges) {
2
    int[] parent = new int[totalNodes + 1];
3
    int[] rank = new int[totalNodes + 1];
4
    int[] size = new int[totalNodes + 1];
5
    boolean[] inEdge = new boolean[totalNodes + 1];
6
    for (int i = 1; i <= totalNodes; i++) {
7
        parent[i] = i;
8
        size[i] = 1;
9
    }
10
    for (int[] e : edges) {
11
        inEdge[e[0]] = inEdge[e[1]] = true;
12
        union(parent, rank, size, e[0], e[1]);
13
    }
14
    int smallest = Integer.MAX_VALUE, largest = 0;
15
    for (int i = 1; i <= totalNodes; i++) {
16
        // Aggregate only at roots, only for labels in edges, only for size ≥ 2.
17
        if (inEdge[i] && find(parent, i) == i && size[i] >= 2) {
18
            smallest = Math.min(smallest, size[i]);
19
            largest = Math.max(largest, size[i]);
20
        }
21
    }
22
    return new int[]{smallest, largest};
23
}
24
 
25
private int find(int[] parent, int x) {
26
    while (parent[x] != x) {
27
        // Compress while climbing; the loop is stack-safe on long chains.
28
        parent[x] = parent[parent[x]];           // path halving, iterative
29
        x = parent[x];
30
    }
31
    return x;
32
}
33
 
34
private void union(int[] parent, int[] rank, int[] size, int a, int b) {
35
    int ra = find(parent, a), rb = find(parent, b);
36
    if (ra == rb) return;
37
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
38
    parent[rb] = ra;
39
    // Only the surviving root's size is updated — non-roots keep stale values.
40
    size[ra] += size[rb];                        // size lives on the root
41
    if (rank[ra] == rank[rb]) rank[ra]++;
42
}

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

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

Carrying size on the root during merges means the answer is one root sweep away. Union-Find's near-constant operations make this the go-to for size/min/max/count over components when the input is an edge list.

ComplexityO(E · α(N)) time, O(N) space — Each union and find is O(α(N)) — inverse Ackermann, effectively constant. E edges give O(E · α(N)); the final root sweep is O(N · α(N)). Space is O(N) for parent, rank, and size arrays.

E · Edge cases and pitfalls7edges = [[1,2]] — Single component of size 2; smallest and largest both 2.Explore edge cases

Edge cases handled

edges = [[1,2]]Single component of size 2; smallest and largest both 2.
duplicate edge [[1,2],[1,2]]Second union finds equal roots → no-op; size stays 2.
one giant chainAll labels merge into one root; smallest == largest == total connected nodes.

Pitfalls

Reading size at a non-root — returns a stale partial size.
Seeding smallest to 0 — it never updates downward.
Recursive find on a long chain — risks stack overflow; use the iterative loop.
Updating size on both roots during a merge — double counts.

Practice

Try the solution yourself

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

Editable code previewpublic int[] componentSizes(int totalNodes, int[][] edges) { int[] parent = new int[totalNodes + 1]; int[] rank = new int[totalNodes + 1]; int[] size = new int[totalNodes + 1]; boolean[] inEdge = new boolean[totalNodes + 1];Explore the playground

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

public int[] componentSizes(int totalNodes, int[][] edges) {
    int[] parent = new int[totalNodes + 1];
    int[] rank = new int[totalNodes + 1];
    int[] size = new int[totalNodes + 1];
    boolean[] inEdge = new boolean[totalNodes + 1];
    for (int i = 1; i <= totalNodes; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    for (int[] e : edges) {
        inEdge[e[0]] = inEdge[e[1]] = true;
        union(parent, rank, size, e[0], e[1]);
    }
    int smallest = Integer.MAX_VALUE, largest = 0;
    for (int i = 1; i <= totalNodes; i++) {
        if (inEdge[i] && find(parent, i) == i && size[i] >= 2) {
            smallest = Math.min(smallest, size[i]);
            largest = Math.max(largest, size[i]);
        }
    }
    return new int[]{smallest, largest};
}

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];                        // size lives on the root
    if (rank[ra] == rank[rb]) rank[ra]++;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Reading size at a non-root

When two sets merge, only the surviving root's size is updated; the absorbed node keeps its old size. Reading size[x] without checking find(x) == x returns a wrong, partial count.

Explore the code comparison

Don't write this

for i in range(1, total_nodes + 1):
    largest = max(largest, size[i])   # size[i] stale unless i is a root

Write this instead

for i in range(1, total_nodes + 1):
    if find(i) == i:                  # only roots carry the true size
        largest = max(largest, size[i])

Seeding smallest to zero

min(0, anything positive) is always 0, so the smallest never changes from its seed. The minimum must start above every possible size — infinity.

Explore the code comparison

Don't write this

int smallest = 0;
smallest = Math.min(smallest, size[i]);   // stuck at 0

Write this instead

int smallest = Integer.MAX_VALUE;
smallest = Math.min(smallest, size[i]);

Recursive find on a long chain

A component can be a chain of tens of thousands of nodes. A recursive find nests one frame per node and overflows the stack; an iterative loop keeps 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])     # 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

Union-Find component sizing, then min/max over roots

Code pattern to memorize

union each edge's endpoints, maintain size[root]
smallest = +inf, largest = 0
for each root r with size[r] >= 2:
    smallest = min(smallest, size[r])
    largest  = max(largest,  size[r])
return (smallest, largest)

Rules to remember

1Only components with ≥ 2 nodes count — every node here appears in some edge, so each component already has at least 2.
2Keep a size array updated only on merges, and read it only at roots — non-roots hold stale sizes.
3The graph is bipartite (left labels 1..N, right labels N+1..2N), but Union-Find does not care about sides — it just merges labels.
4Use path compression + union by rank so each operation is O(α(N)), effectively constant.
5find climbs parents in a loop — iterative, so a long chain cannot overflow the call stack.

Use this pattern when

You only need component **sizes or membership**, not paths or distances
Edges arrive as a flat list and you merge groups incrementally
Min/max/count over connected components
Bipartite or general undirected graphs where sides are irrelevant to connectivity

Choose another pattern when

You need shortest paths or distances → BFS/Dijkstra, not Union-Find
You must enumerate the actual members of each component → DFS/BFS flood fill is more natural
Edges are removed over time → Union-Find does not support deletion cleanly
You need the bipartite structure itself (2-coloring) → bipartite check, not sizing

Interview takeaway

Union-Find turns a flat edge list into component sizes in near-constant time per edge. Carry the size on the root during merges, then a single sweep over roots gives any aggregate you need — here the smallest and largest.

Continue

Transfer the pattern to another problem

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

Transferable patternUnion-Find Component Sizing with Aggregation. Recognize it when an edge list defines groups and you need a size aggregate — min, max, count, or per-group value. Carry size on the root during merges, sweep roots once. The same skeleton powers Number of Connected Components, Journey to the Moon, and Roads and Libraries.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

BFS: Shortest Reach in a Graph

Continue · Next problem

Dijkstra: Shortest Reach 2

mediumGraphsSometimes asked

Components in a Graph

Graphs · 22 of 34 · 11 min

There are 2 × N nodes in an undirected graph, labeled 1 to 2N. Each edge connects a node from the left set (1..N) to a node from the right set (N+1..2N). You are given a list of edges.

Return two values: the size of the smallest connected component and the size of the largest connected component, considering only components that contain at least two nodes.

In plain English

Examples

Example 1

Input: edges = [[1,6],[2,7],[3,8],[4,9],[2,6]]
Output: 2 4
Note: Edge 2–6 links the {1,6} and {2,7} groups into {1,2,6,7} (size 4). {3,8} and {4,9} stay size 2. Smallest 2, largest 4.

Example 2

Input: edges = [[1,5],[1,6],[2,4]]
Output: 2 3
Note: {1,5,6} has size 3, {2,4} has size 2. Smallest 2, largest 3.

Example 3

Input: edges = [[1,2]]
Output: 2 2
Note: A single component of size 2 — smallest and largest coincide.

Constraints

1 ≤ N ≤ 1.5 × 10⁴ (so up to 3 × 10⁴ node labels)
1 ≤ edges.length ≤ 10⁵
Each edge's left endpoint is in 1..N, right endpoint in N+1..2N
The graph is undirected; isolated nodes (in no edge) are ignored
At least one edge exists, so at least one component of size ≥ 2 exists

Clarifying questions4First question: Do isolated nodes count as size-1 components?Explore questions

Q1.Do isolated nodes count as size-1 components?
No. The problem only considers components with at least two nodes, and every node in an edge is already in one. Untouched labels are ignored.
Q2.Does the bipartite structure matter to the algorithm?
Not for sizing. Union-Find merges whatever labels an edge connects; the left/right split is irrelevant to connected components.
Q3.Can the same edge appear twice?
Yes, and it is harmless — a union whose endpoints already share a root does nothing.
Q4.Could there be a single giant component?
Yes — then smallest and largest are equal. Seed smallest to infinity so a lone component still sets both.

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 reach for Union-Find with size tracking on a connectivity-only question, read sizes only at roots, and correctly aggregate the min and max across components.

Where candidates slip

Reading the size array at a non-root node (stale value), counting isolated nodes that should be excluded, or initializing 'smallest' to 0 so it never updates.

How to stand out

Maintain size on merge, sweep only roots, seed smallest to +infinity, and note that the bipartite labeling is irrelevant to the merging — it is just an undirected graph.

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 Flood Fill (Baseline)	`O(V + E)`	`O(V + E)`	A natural first take: build an adjacency list, flood-fill each unvisited node to measure its component, and track the min and max sizes. Correct and intuitive.	Read
2	Union-Find with Size Tracking (Optimal)Optimal	`O(E · α(N))`	`O(N)`	The cleanest answer for a flat edge list. Union each edge, carry size on each root, then sweep roots for the smallest and largest.	Read

Three components of sizes 4, 2, 2

How to read it:Edge 2–6 fuses two pairs into a size-4 component; the others stay at size 2.

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 Flood Fill (Baseline)

TimeO(V + E)SpaceO(V + E)

A natural first take: build an adjacency list, flood-fill each unvisited node to measure its component, and track the min and max sizes. Correct and intuitive.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What do you need per component? Just its node count. How do you count every node reachable from a start?

2Hint 2Explore hint

Build an adjacency list, then walk each unvisited node, flood-filling its whole component and counting how many nodes it touches.

3Hint 3Explore hint

Track the smallest and largest counts among components with size ≥ 2 as you discover them.

A · Core idea

If the only quantity you need is each component's size, a flood fill delivers it directly.

B · Visual dry run

Interactive dry run

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

edges = [[1,5],[1,6],[2,4]]

Interactive diagram

Flood fill measuring a component

flood from 1

Active call / nodeSupporting contextReturned stateNot active

From node 1 the walk reaches 5 and 6 — size 3.

Final result2 3

C · Code with teaching comments

solution.javaJava

DFS / BFS Flood Fill (Baseline) — reference

3 teaching notes

1
public int[] componentSizes(int totalNodes, int[][] edges) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i <= totalNodes; i++) adj.add(new ArrayList<>());
4
    boolean[] inEdge = new boolean[totalNodes + 1];
5
    for (int[] e : edges) {
6
        adj.get(e[0]).add(e[1]);
7
        adj.get(e[1]).add(e[0]);
8
        inEdge[e[0]] = true;
9
        inEdge[e[1]] = true;
10
    }
11
    boolean[] visited = new boolean[totalNodes + 1];
12
    int smallest = Integer.MAX_VALUE, largest = 0;
13
    for (int start = 1; start <= totalNodes; start++) {
14
        if (!inEdge[start] || visited[start]) continue;
15
        int size = 0;
16
        Deque<Integer> stack = new ArrayDeque<>();
17
        stack.push(start);
18
        visited[start] = true;
19
        // Explicit stack keeps depth on the heap — safe for long-chain components.
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
        // Only components with at least two nodes count toward the answer.
31
        if (size >= 2) {
32
            smallest = Math.min(smallest, size);
33
            largest = Math.max(largest, size);
34
        }
35
    }
36
    return new int[]{smallest, largest};
37
}

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

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

The problem reduces to component sizes; a flood fill produces them in one linear pass. The only subtlety is aggregating correctly — seed the minimum to infinity so it can actually shrink.

E · Edge cases and pitfalls3Recursive DFS on a long chain — stack overflow.Explore edge cases

Pitfalls

Recursive DFS on a long chain — stack overflow.
Seeding smallest to 0 — it can never decrease below 0, so it never updates.
Counting isolated nodes as size-1 components when the problem excludes them.

03.2

Approach 2 of 2 · Optimal

Union-Find with Size Tracking (Optimal)

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

The cleanest answer for a flat edge list. Union each edge, carry size on each root, then sweep roots for the smallest and largest.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You only need sizes, never paths. What structure merges groups and tracks their sizes in near-constant time per edge?

2Hint 2Explore hint

Union-Find: union each edge's endpoints with path compression and union by rank, and add the merged sizes onto the surviving root.

3Hint 3Explore hint

After all unions, scan the labels; for each label that is its own root, its size is its component size. Take the min and max over roots of size ≥ 2.

A · Core idea

Union-Find is the natural fit when edges arrive as a list and you only care about group sizes.

B · Visual dry run

Interactive dry run

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

edges = [[1,6],[2,7],[3,8],[4,9],[2,6]]

Interactive diagram

Disjoint-set forest after all unions

union 1-6, 2-7, 3-8, 4-9

Active call / nodeSupporting contextReturned stateNot active

Root of the size-4 set holds size 4; the two size-2 sets hold 2 each.

Final result2 4

C · Code with teaching comments

solution.javaJava

Union-Find with Size Tracking (Optimal) — optimal

3 teaching notes

1
public int[] componentSizes(int totalNodes, int[][] edges) {
2
    int[] parent = new int[totalNodes + 1];
3
    int[] rank = new int[totalNodes + 1];
4
    int[] size = new int[totalNodes + 1];
5
    boolean[] inEdge = new boolean[totalNodes + 1];
6
    for (int i = 1; i <= totalNodes; i++) {
7
        parent[i] = i;
8
        size[i] = 1;
9
    }
10
    for (int[] e : edges) {
11
        inEdge[e[0]] = inEdge[e[1]] = true;
12
        union(parent, rank, size, e[0], e[1]);
13
    }
14
    int smallest = Integer.MAX_VALUE, largest = 0;
15
    for (int i = 1; i <= totalNodes; i++) {
16
        // Aggregate only at roots, only for labels in edges, only for size ≥ 2.
17
        if (inEdge[i] && find(parent, i) == i && size[i] >= 2) {
18
            smallest = Math.min(smallest, size[i]);
19
            largest = Math.max(largest, size[i]);
20
        }
21
    }
22
    return new int[]{smallest, largest};
23
}
24
 
25
private int find(int[] parent, int x) {
26
    while (parent[x] != x) {
27
        // Compress while climbing; the loop is stack-safe on long chains.
28
        parent[x] = parent[parent[x]];           // path halving, iterative
29
        x = parent[x];
30
    }
31
    return x;
32
}
33
 
34
private void union(int[] parent, int[] rank, int[] size, int a, int b) {
35
    int ra = find(parent, a), rb = find(parent, b);
36
    if (ra == rb) return;
37
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
38
    parent[rb] = ra;
39
    // Only the surviving root's size is updated — non-roots keep stale values.
40
    size[ra] += size[rb];                        // size lives on the root
41
    if (rank[ra] == rank[rb]) rank[ra]++;
42
}

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

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

E · Edge cases and pitfalls7edges = [[1,2]] — Single component of size 2; smallest and largest both 2.Explore edge cases

Edge cases handled

edges = [[1,2]]Single component of size 2; smallest and largest both 2.
duplicate edge [[1,2],[1,2]]Second union finds equal roots → no-op; size stays 2.
one giant chainAll labels merge into one root; smallest == largest == total connected nodes.

Pitfalls

Reading size at a non-root — returns a stale partial size.
Seeding smallest to 0 — it never updates downward.
Recursive find on a long chain — risks stack overflow; use the iterative loop.
Updating size on both roots during a merge — double counts.

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.

Reading size at a non-root

When two sets merge, only the surviving root's size is updated; the absorbed node keeps its old size. Reading size[x] without checking find(x) == x returns a wrong, partial count.

Explore the code comparison

Don't write this

for i in range(1, total_nodes + 1):
    largest = max(largest, size[i])   # size[i] stale unless i is a root

Write this instead

for i in range(1, total_nodes + 1):
    if find(i) == i:                  # only roots carry the true size
        largest = max(largest, size[i])

Seeding smallest to zero

min(0, anything positive) is always 0, so the smallest never changes from its seed. The minimum must start above every possible size — infinity.

Explore the code comparison

Don't write this

int smallest = 0;
smallest = Math.min(smallest, size[i]);   // stuck at 0

Write this instead

int smallest = Integer.MAX_VALUE;
smallest = Math.min(smallest, size[i]);

Recursive find on a long chain

A component can be a chain of tens of thousands of nodes. A recursive find nests one frame per node and overflows the stack; an iterative loop keeps 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])     # 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

Union-Find component sizing, then min/max over roots

Code pattern to memorize

union each edge's endpoints, maintain size[root]
smallest = +inf, largest = 0
for each root r with size[r] >= 2:
    smallest = min(smallest, size[r])
    largest  = max(largest,  size[r])
return (smallest, largest)

Rules to remember

1Only components with ≥ 2 nodes count — every node here appears in some edge, so each component already has at least 2.
2Keep a size array updated only on merges, and read it only at roots — non-roots hold stale sizes.
3The graph is bipartite (left labels 1..N, right labels N+1..2N), but Union-Find does not care about sides — it just merges labels.
4Use path compression + union by rank so each operation is O(α(N)), effectively constant.
5find climbs parents in a loop — iterative, so a long chain cannot overflow the call stack.

Use this pattern when

You only need component **sizes or membership**, not paths or distances
Edges arrive as a flat list and you merge groups incrementally
Min/max/count over connected components
Bipartite or general undirected graphs where sides are irrelevant to connectivity

Choose another pattern when

You need shortest paths or distances → BFS/Dijkstra, not Union-Find
You must enumerate the actual members of each component → DFS/BFS flood fill is more natural
Edges are removed over time → Union-Find does not support deletion cleanly
You need the bipartite structure itself (2-coloring) → bipartite check, not sizing

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

←

BFS: Shortest Reach in a Graph

Continue · Next problem

Dijkstra: Shortest Reach 2