Loading…

mediumGraphsFrequently asked

Friend Circle Queries

Q: How do you solve Friend Circle Queries using the Explicit-Set Merge (Baseline) approach?

When to use it: Mention the literal model first: keep each circle as an actual set, and on a query merge one set into the other, repointing every moved member. Simple, but each merge can touch many members. The most direct model treats each friend circle as a concrete collection of people. **The structure.** A hash map `circleOf` maps each person to the set object representing their circle. New people start in a fresh singleton set. **Per query.** For `(a, b)`, fetch both sets. If they're the same object, it's a no-op. Otherwise merge: iterate over the members of one set, add each to the other, and update its `circleOf` pointer to the surviving set. The surviving set's size is the sum; update the global `best` and append it. **Why it's correct.** Sets exactly represent connected components: merging two sets on an edge models transitive friendship precisely, and the size of the largest set is the answer. **Why we don't ship it.** Pouring all members of one set into another costs time proportional to that set's size. If you don't consistently move the *smaller* set, a chain of merges can re-move the same elements over and over — O(q · n). Union-find replaces whole-set copying with a single pointer update, dropping each operation to near-O(1). Time complexity: O(q · n) worst case. Space complexity: O(n).

Q: How do you solve Friend Circle Queries using the Union-Find with Size (Optimal) approach?

When to use it: The intended solution. Phrase it as 'hash-map disjoint set with union by size and path compression; track a running max that updates only on a real merge'. Union-find turns whole-set merging into a single pointer change, keeping circle sizes on the roots. **The structure.** Two hash maps: `parent[x]` (the parent pointer; a root points to itself) and `size[r]` (members in the circle rooted at `r`). The first time a person is seen, `find` creates them as a singleton — `parent[x] = x`, `size[x] = 1`. **find with path compression.** `find(x)` walks parent pointers to the root and compresses the path so future lookups are near-constant. **union by size.** For query `(a, b)`, compute roots `ra, rb`. If equal, the two are already in one circle — a no-op. Otherwise attach the smaller-size root under the larger and add the sizes. Union by size keeps the trees shallow, which (with path compression) gives the inverse-Ackermann bound. **The running max.** The largest circle can only change when two different circles merge, and the only candidate for a new maximum is the just-merged circle's size. So after a real union, `best = max(best, size[newRoot])`; on a no-op, `best` is unchanged. Append `best` after every query — including no-ops — to produce exactly `q` outputs. **Why hash maps.** IDs reach 10⁹ and are sparse, so an array of that size is infeasible. Hash maps store only the people actually involved, with lazy singleton creation on first contact. Time complexity: O(q · α(n)) ≈ O(q). Space complexity: O(n).

Graphs · 31 of 34 · 11 min

You are given a list of q queries. Each query is a pair (a, b) declaring that persons a and b are now friends. Friendship is transitive: if a–b and b–c are friends, then a, b, c form one friend circle.

After processing each query, record the size of the largest friend circle that exists at that moment. Return the list of these maxima, one per query.

In plain English

People are nodes; each query adds an undirected edge, and a friend circle is a connected component. The twist is that everything is online — edges arrive one at a time and after each you must answer 'biggest circle so far'. Re-scanning the whole graph per query is too slow at 10⁵ queries. Union-find merges circles in near-constant time and, by storing each circle's size on its root, lets you track the largest size as a running maximum: it can only grow, and only when a query actually fuses two previously-separate circles. The huge id space forces a hash-map-backed DSU rather than plain arrays.

Examples

Example 1

Input: queries = [[1,2],[3,4],[2,3]]
Output: [2, 2, 4]
Note: After (1,2): circle {1,2} size 2 → max 2. After (3,4): circles {1,2},{3,4} both size 2 → max 2. After (2,3): they merge into {1,2,3,4} size 4 → max 4.

Example 2

Input: queries = [[1,2],[1,2],[5,6]]
Output: [2, 2, 2]
Note: Second (1,2) is a no-op (same circle), max stays 2. (5,6) forms another size-2 circle; max is still 2.

Example 3

Input: queries = [[100,200],[200,300],[300,400]]
Output: [2, 3, 4]
Note: A growing chain: sizes 2, then 3, then 4. Large sparse IDs handled by hash-map DSU.

Constraints

1 ≤ q ≤ 10⁵ queries
1 ≤ a, b ≤ 10⁹ (person IDs are large and sparse)
a ≠ b within a query (or, if equal, the union is a harmless no-op)
Friendships are permanent and undirected (never removed)
Output has exactly q entries — the running max after each query

Clarifying questions4First question: Do I report the max after every query, or only at the end?Explore questions

Q1.Do I report the max after every query, or only at the end?
After every query — the output is a list of q running maxima.
Q2.How large are the person IDs?
Up to 10⁹ and sparse, so I'll back the disjoint set with hash maps and create singletons lazily.
Q3.What if both people are already in the same circle?
The union is a no-op; the largest size is unchanged, but I still append the current max for that query.
Q4.Can friendships be removed?
No — they're permanent. Union-find only supports merging, which is exactly enough here.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each query (a, b) makes a and b friends; friendship is transitive, forming circles. After each query, report the size of the largest circle so far. Use union-find with a size per component and union by size: when two distinct circles merge, the new size is the sum; keep a running max and append it after every query. Because person IDs can be up to 10⁹, back the disjoint set with hash maps, not arrays. O(q · α) ≈ O(q).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model incremental friend-merging as union-find, augment it with per-component size, and maintain the largest size as a running max — using hash maps because IDs are large.

Where candidates slip

Recomputing component sizes by BFS after each query (O(q·n)), updating the max on no-op unions, forgetting union by size / path compression, or assuming small array-indexable IDs.

How to stand out

Note that the max only changes on a real merge, use union by size + path compression for the inverse-Ackermann bound, and explain why a hash-map DSU is required for a 10⁹ id space.

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	Explicit-Set Merge (Baseline)	`O(q · n) worst case`	`O(n)`	Mention the literal model first: keep each circle as an actual set, and on a query merge one set into the other, repointing every moved member. Simple, but each merge can touch many members.	Read
2	Union-Find with Size (Optimal)Optimal	`O(q · α(n)) ≈ O(q)`	`O(n)`	The intended solution. Phrase it as 'hash-map disjoint set with union by size and path compression; track a running max that updates only on a real merge'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewOnline merging + largest-group query?Edges removed ever?YesNoExplore the full tree

Circles merging across the sample queries

How to read it:Query (2,3) fuses two size-2 circles into one size-4 circle — the moment the running max jumps to 4.

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

Explicit-Set Merge (Baseline)

TimeO(q · n) worst caseSpaceO(n)

Mention the literal model first: keep each circle as an actual set, and on a query merge one set into the other, repointing every moved member. Simple, but each merge can touch many members.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Model a circle as a real set of members, and keep a map from each person to the set they belong to.

2Hint 2Explore hint

On query (a, b): if they're in different sets, pour the members of one set into the other and update each moved member's pointer; track the new size and the global max.

3Hint 3Explore hint

Merging without choosing the smaller side can move many members repeatedly → O(n) per merge in the worst case. Correct, but it motivates union-find.

A · Core idea

The most direct model treats each friend circle as a concrete collection of people.

The structure. A hash map circleOf maps each person to the set object representing their circle. New people start in a fresh singleton set.

Per query. For (a, b), fetch both sets. If they're the same object, it's a no-op. Otherwise merge: iterate over the members of one set, add each to the other, and update its circleOf pointer to the surviving set. The surviving set's size is the sum; update the global best and append it.

Why it's correct. Sets exactly represent connected components: merging two sets on an edge models transitive friendship precisely, and the size of the largest set is the answer.

Why we don't ship it. Pouring all members of one set into another costs time proportional to that set's size. If you don't consistently move the smaller set, a chain of merges can re-move the same elements over and over — O(q · n). Union-find replaces whole-set copying with a single pointer update, dropping each operation to near-O(1).

B · Visual dry run

Interactive dry run

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

queries = [[1,2],[3,4],[2,3]]

Array state

(1,2)

{1,2}

[0]

Current pointerResolved stateNot processed

Final result[2, 2, 4]

C · Code with teaching comments

Reference implementation previewpublic int[] maxCircle(int[][] queries) { Map<Integer, Set<Integer>> circleOf = new HashMap<>(); int[] result = new int[queries.length]; int best = 0; for (int qi = 0; qi < queries.length; qi++) {Explore the full code

solution.javaJava

Explicit-Set Merge (Baseline) — reference

3 teaching notes

1
public int[] maxCircle(int[][] queries) {
2
    Map<Integer, Set<Integer>> circleOf = new HashMap<>();
3
    int[] result = new int[queries.length];
4
    int best = 0;
5
    for (int qi = 0; qi < queries.length; qi++) {
6
        int a = queries[qi][0], b = queries[qi][1];
7
        // Lazily create a singleton circle the first time a person appears.
8
        Set<Integer> sa = circleOf.computeIfAbsent(a, x -> new HashSet<>(Set.of(x)));
9
        Set<Integer> sb = circleOf.computeIfAbsent(b, x -> new HashSet<>(Set.of(x)));
10
        if (sa != sb) {
11
            // Move the smaller set into the larger (small-to-large) to limit member
12
            // copying.
13
            if (sa.size() < sb.size()) { Set<Integer> t = sa; sa = sb; sb = t; }
14
            for (int member : sb) {       // pour smaller set into larger
15
                sa.add(member);
16
                circleOf.put(member, sa);
17
            }
18
            // Only a real merge can grow the largest circle.
19
            best = Math.max(best, sa.size());
20
        }
21
        result[qi] = best;
22
    }
23
    return result;
24
}

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

D · Why it works and complexityO(q · n) worst case timeO(n) spaceOpen the invariant and proofExplore the proof

Explicit-set merging makes the model obvious, and even reveals the key optimization: always move the smaller set (small-to-large) to bound the work. Union-find generalizes that intuition with union by size plus path compression, avoiding member copying entirely.

ComplexityO(q · n) worst case time, O(n) space — Each merge copies the members of one circle into another and repoints them. Without always moving the smaller side, a single person can be moved up to n times across q queries, giving O(q · n) worst case. Lookups are O(1) via the person→set map. Correct and intuitive, but quadratic in adversarial inputs.

E · Edge cases and pitfalls3Merging without small-to-large — re-moves members and degrades to O(q·n).Explore edge cases

Pitfalls

Merging without small-to-large — re-moves members and degrades to O(q·n).
Updating best on a no-op (same-set) query.
Assuming small IDs and indexing an array instead of a map.

03.2

Approach 2 of 2 · Optimal

Union-Find with Size (Optimal)

TimeO(q · α(n)) ≈ O(q)SpaceO(n)

The intended solution. Phrase it as 'hash-map disjoint set with union by size and path compression; track a running max that updates only on a real merge'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of copying members, can each circle be a tree of parent pointers so a merge is one pointer update?

2Hint 2Explore hint

Union-find: find(x) returns the root (circle id) with path compression; union(a, b) links the smaller-size root under the larger and adds the sizes.

3Hint 3Explore hint

Keep size[root] for each circle and a running best. On a real merge, best = max(best, new size). Append best after each query. Back parent/size with hash maps for the 10⁹ id space.

A · Core idea

Union-find turns whole-set merging into a single pointer change, keeping circle sizes on the roots.

The structure. Two hash maps: parent[x] (the parent pointer; a root points to itself) and size[r] (members in the circle rooted at r). The first time a person is seen, find creates them as a singleton — parent[x] = x, size[x] = 1.

find with path compression. find(x) walks parent pointers to the root and compresses the path so future lookups are near-constant.

union by size. For query (a, b), compute roots ra, rb. If equal, the two are already in one circle — a no-op. Otherwise attach the smaller-size root under the larger and add the sizes. Union by size keeps the trees shallow, which (with path compression) gives the inverse-Ackermann bound.

The running max. The largest circle can only change when two different circles merge, and the only candidate for a new maximum is the just-merged circle's size. So after a real union, best = max(best, size[newRoot]); on a no-op, best is unchanged. Append best after every query — including no-ops — to produce exactly q outputs.

Why hash maps. IDs reach 10⁹ and are sparse, so an array of that size is infeasible. Hash maps store only the people actually involved, with lazy singleton creation on first contact.

B · Visual dry run

Interactive dry run

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

queries = [[1,2],[3,4],[2,3]]

Array state

(1,2)

size 2, best 2

[0]

Current pointerResolved stateNot processed

Final result[2, 2, 4]

C · Code with teaching comments

solution.javaJava

Union-Find with Size (Optimal) — optimal

4 teaching notes

1
private Map<Integer, Integer> parent = new HashMap<>();
2
private Map<Integer, Integer> size = new HashMap<>();
3
 
4
private int find(int x) {
5
    // Lazily register a never-seen person as their own singleton root.
6
    parent.putIfAbsent(x, x);
7
    size.putIfAbsent(x, 1);
8
    int root = x;
9
    while (parent.get(root) != root) root = parent.get(root);
10
    // Re-point every node on the path directly to the root to flatten future finds.
11
    while (parent.get(x) != root) {        // path compression
12
        int next = parent.get(x);
13
        parent.put(x, root);
14
        x = next;
15
    }
16
    return root;
17
}
18
 
19
public int[] maxCircle(int[][] queries) {
20
    int[] result = new int[queries.length];
21
    int best = 0;
22
    for (int qi = 0; qi < queries.length; qi++) {
23
        int ra = find(queries[qi][0]);
24
        int rb = find(queries[qi][1]);
25
        if (ra != rb) {
26
            // Union by size: attach the smaller circle under the larger.
27
            if (size.get(ra) < size.get(rb)) { int t = ra; ra = rb; rb = t; }
28
            parent.put(rb, ra);             // union by size
29
            int merged = size.get(ra) + size.get(rb);
30
            size.put(ra, merged);
31
            // The only candidate for a new global max is the freshly merged circle.
32
            best = Math.max(best, merged);
33
        }
34
        result[qi] = best;
35
    }
36
    return result;
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(q · α(n)) ≈ O(q) timeO(n) spaceOpen the invariant and proofExplore the proof

Augmenting union-find's roots with a size is the lever that answers aggregate questions ('largest circle', 'is this group big enough?') in O(1) per merge. Combined with the observation that the global max only moves on a real merge, the whole problem collapses to one running maximum updated alongside the unions.

ComplexityO(q · α(n)) ≈ O(q) time, O(n) space — Each query does two finds and at most one union. With path compression and union by size, those are O(α(n)) amortized (inverse Ackermann ≤ 4 in practice). So all q queries cost O(q · α(n)) ≈ O(q). Hash-map operations are O(1) average. Space is O(n) for the parent and size maps over the distinct people seen.

E · Edge cases and pitfalls7duplicate query (1,2) then (1,2) — Second union finds equal roots → no-op; best unchanged but still appended.Explore edge cases

Edge cases handled

duplicate query (1,2) then (1,2)Second union finds equal roots → no-op; best unchanged but still appended.
query (5, 5) (same person)find(5) == find(5) → no merge; size stays 1, best unaffected.
all distinct pairs, no overlapsEvery circle is size 2; best is 2 after the first query and stays 2.

Pitfalls

Updating best on a no-op union (same root).
Skipping union by size and/or path compression — finds degrade toward O(n).
Using arrays for parent/size when IDs reach 10⁹.
Re-deriving the max by scanning all components each query — that's O(q·n).

Practice

Try the solution yourself

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

Editable code previewprivate Map<Integer, Integer> parent = new HashMap<>(); private Map<Integer, Integer> size = new HashMap<>(); private int find(int x) { parent.putIfAbsent(x, x);Explore the playground

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

private Map<Integer, Integer> parent = new HashMap<>();
private Map<Integer, Integer> size = new HashMap<>();

private int find(int x) {
    parent.putIfAbsent(x, x);
    size.putIfAbsent(x, 1);
    int root = x;
    while (parent.get(root) != root) root = parent.get(root);
    while (parent.get(x) != root) {        // path compression
        int next = parent.get(x);
        parent.put(x, root);
        x = next;
    }
    return root;
}

public int[] maxCircle(int[][] queries) {
    int[] result = new int[queries.length];
    int best = 0;
    for (int qi = 0; qi < queries.length; qi++) {
        int ra = find(queries[qi][0]);
        int rb = find(queries[qi][1]);
        if (ra != rb) {
            if (size.get(ra) < size.get(rb)) { int t = ra; ra = rb; rb = t; }
            parent.put(rb, ra);             // union by size
            int merged = size.get(ra) + size.get(rb);
            size.put(ra, merged);
            best = Math.max(best, merged);
        }
        result[qi] = best;
    }
    return result;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Max updated on a no-op union

If a and b are already in the same circle, nothing merges. Touching best (or re-adding size) here can overcount, and re-summing sizes corrupts the component size.

Explore the code comparison

Don't write this

ra, rb = find(a), find(b)
parent[rb] = ra            # blindly unions even if ra == rb
size[ra] += size[rb]
best = max(best, size[ra])

Write this instead

ra, rb = find(a), find(b)
if ra != rb:               # only on a real merge
    parent[rb] = ra
    size[ra] += size[rb]
    best = max(best, size[ra])

Array DSU with huge IDs

IDs reach 10⁹, so new int[10⁹] is infeasible (memory) — and even compressing requires a map. A hash-map DSU stores only the people actually seen.

Explore the code comparison

Don't write this

int[] parent = new int[1_000_000_001];   // out of memory

Write this instead

Map<Integer, Integer> parent = new HashMap<>();   // lazy, sparse

Rescanning for the max

Deriving the largest circle by iterating all components after each query is O(n) per query → O(q·n). Maintaining a running max updated on each real merge is O(1).

Explore the code comparison

Don't write this

result.append(max(size[find(p)] for p in all_people))  # O(n) per query

Write this instead

best = max(best, size[ra])   # O(1) update on merge
result.append(best)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Union-find with component sizes + running max

Code pattern to memorize

parent = {}, size = {}, best = 0
for (a, b) in queries:
    ra, rb = find(a), find(b)        # find auto-creates new singletons (size 1)
    if ra != rb:
        if size[ra] < size[rb]: swap(ra, rb)
        parent[rb] = ra
        size[ra] += size[rb]
        best = max(best, size[ra])
    append best
return results

Rules to remember

1Track a size per root and merge smaller into larger (union by size) to keep trees shallow.
2Maintain a running max circle size; update it only when a union actually merges two different circles.
3Person IDs are huge (up to 10⁹) → back parent/size with hash maps, lazily creating a singleton (size 1) on first sight.
4A query joining two people already in the same circle changes nothing — best stays the same; still append it.
5Append the current best after every query, including no-op unions.

Use this pattern when

Incremental **merging** of groups with a 'largest group so far' question
Dynamic connectivity: edges arrive online, queries interleave
Sparse / large id space where arrays won't fit → hash-map DSU
You only need group *sizes/connectivity*, not paths or distances

Choose another pattern when

Edges are *removed* over time → union-find can't undo; use other structures (or offline + reverse)
You need shortest paths or weighted distances → Dijkstra/BFS, not DSU
A static graph asked once → a single BFS/DFS pass suffices
You must enumerate each group's members repeatedly → maintain explicit lists, not just sizes

Interview takeaway

Union-find is the canonical tool for online merging plus connectivity. Augmenting each root with a size turns 'how big is the largest group?' into an O(1) running maximum updated on each real merge — the standard pattern behind friend circles, islands that grow, and accounts-merge problems.

Continue

Transfer the pattern to another problem

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

Transferable patternCanonical Union-Find with Augmented Size. Recognize it on online merging plus an aggregate query ('largest group', 'still connected?'). Store size on roots, union by size with path compression, and keep a running max updated only on real merges. Use a hash-map-backed DSU whenever the id space is too large or sparse for arrays.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of Connected Components
Same union-find; track a component counter that decrements on each real merge instead of a max size.
Accounts Merge
Coming soon
Union-find over emails to merge accounts sharing any address, then group members by root.
Number of Islands II
Coming soon
Online land additions on a grid — union neighbors and report the island count after each addition.
Kruskal (MST): Really Special Subtree
Union-find as the cycle-detection engine while greedily adding the cheapest edges.

Same pattern

←

Floyd: City of Blinding Lights

Continue · Next problem

Kruskal (MST): Really Special Subtree

mediumGraphsFrequently asked

Friend Circle Queries

Graphs · 31 of 34 · 11 min

After processing each query, record the size of the largest friend circle that exists at that moment. Return the list of these maxima, one per query.

In plain English

Examples

Example 1

Input: queries = [[1,2],[3,4],[2,3]]
Output: [2, 2, 4]
Note: After (1,2): circle {1,2} size 2 → max 2. After (3,4): circles {1,2},{3,4} both size 2 → max 2. After (2,3): they merge into {1,2,3,4} size 4 → max 4.

Example 2

Input: queries = [[1,2],[1,2],[5,6]]
Output: [2, 2, 2]
Note: Second (1,2) is a no-op (same circle), max stays 2. (5,6) forms another size-2 circle; max is still 2.

Example 3

Input: queries = [[100,200],[200,300],[300,400]]
Output: [2, 3, 4]
Note: A growing chain: sizes 2, then 3, then 4. Large sparse IDs handled by hash-map DSU.

Constraints

1 ≤ q ≤ 10⁵ queries
1 ≤ a, b ≤ 10⁹ (person IDs are large and sparse)
a ≠ b within a query (or, if equal, the union is a harmless no-op)
Friendships are permanent and undirected (never removed)
Output has exactly q entries — the running max after each query

Clarifying questions4First question: Do I report the max after every query, or only at the end?Explore questions

Q1.Do I report the max after every query, or only at the end?
After every query — the output is a list of q running maxima.
Q2.How large are the person IDs?
Up to 10⁹ and sparse, so I'll back the disjoint set with hash maps and create singletons lazily.
Q3.What if both people are already in the same circle?
The union is a no-op; the largest size is unchanged, but I still append the current max for that query.
Q4.Can friendships be removed?
No — they're permanent. Union-find only supports merging, which is exactly enough here.

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 model incremental friend-merging as union-find, augment it with per-component size, and maintain the largest size as a running max — using hash maps because IDs are large.

Where candidates slip

Recomputing component sizes by BFS after each query (O(q·n)), updating the max on no-op unions, forgetting union by size / path compression, or assuming small array-indexable IDs.

How to stand out

Note that the max only changes on a real merge, use union by size + path compression for the inverse-Ackermann bound, and explain why a hash-map DSU is required for a 10⁹ id space.

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	Explicit-Set Merge (Baseline)	`O(q · n) worst case`	`O(n)`	Mention the literal model first: keep each circle as an actual set, and on a query merge one set into the other, repointing every moved member. Simple, but each merge can touch many members.	Read
2	Union-Find with Size (Optimal)Optimal	`O(q · α(n)) ≈ O(q)`	`O(n)`	The intended solution. Phrase it as 'hash-map disjoint set with union by size and path compression; track a running max that updates only on a real merge'.	Read

Circles merging across the sample queries

How to read it:Query (2,3) fuses two size-2 circles into one size-4 circle — the moment the running max jumps to 4.

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

Explicit-Set Merge (Baseline)

TimeO(q · n) worst caseSpaceO(n)

Mention the literal model first: keep each circle as an actual set, and on a query merge one set into the other, repointing every moved member. Simple, but each merge can touch many members.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Model a circle as a real set of members, and keep a map from each person to the set they belong to.

2Hint 2Explore hint

On query (a, b): if they're in different sets, pour the members of one set into the other and update each moved member's pointer; track the new size and the global max.

3Hint 3Explore hint

Merging without choosing the smaller side can move many members repeatedly → O(n) per merge in the worst case. Correct, but it motivates union-find.

A · Core idea

The most direct model treats each friend circle as a concrete collection of people.

The structure. A hash map circleOf maps each person to the set object representing their circle. New people start in a fresh singleton set.

Why it's correct. Sets exactly represent connected components: merging two sets on an edge models transitive friendship precisely, and the size of the largest set is the answer.

B · Visual dry run

Interactive dry run

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

queries = [[1,2],[3,4],[2,3]]

Array state

(1,2)

{1,2}

[0]

Current pointerResolved stateNot processed

Final result[2, 2, 4]

C · Code with teaching comments

solution.javaJava

Explicit-Set Merge (Baseline) — reference

3 teaching notes

1
public int[] maxCircle(int[][] queries) {
2
    Map<Integer, Set<Integer>> circleOf = new HashMap<>();
3
    int[] result = new int[queries.length];
4
    int best = 0;
5
    for (int qi = 0; qi < queries.length; qi++) {
6
        int a = queries[qi][0], b = queries[qi][1];
7
        // Lazily create a singleton circle the first time a person appears.
8
        Set<Integer> sa = circleOf.computeIfAbsent(a, x -> new HashSet<>(Set.of(x)));
9
        Set<Integer> sb = circleOf.computeIfAbsent(b, x -> new HashSet<>(Set.of(x)));
10
        if (sa != sb) {
11
            // Move the smaller set into the larger (small-to-large) to limit member
12
            // copying.
13
            if (sa.size() < sb.size()) { Set<Integer> t = sa; sa = sb; sb = t; }
14
            for (int member : sb) {       // pour smaller set into larger
15
                sa.add(member);
16
                circleOf.put(member, sa);
17
            }
18
            // Only a real merge can grow the largest circle.
19
            best = Math.max(best, sa.size());
20
        }
21
        result[qi] = best;
22
    }
23
    return result;
24
}

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

D · Why it works and complexityO(q · n) worst case timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Merging without small-to-large — re-moves members and degrades to O(q·n).Explore edge cases

Pitfalls

Merging without small-to-large — re-moves members and degrades to O(q·n).
Updating best on a no-op (same-set) query.
Assuming small IDs and indexing an array instead of a map.

03.2

Approach 2 of 2 · Optimal

Union-Find with Size (Optimal)

TimeO(q · α(n)) ≈ O(q)SpaceO(n)

The intended solution. Phrase it as 'hash-map disjoint set with union by size and path compression; track a running max that updates only on a real merge'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of copying members, can each circle be a tree of parent pointers so a merge is one pointer update?

2Hint 2Explore hint

Union-find: find(x) returns the root (circle id) with path compression; union(a, b) links the smaller-size root under the larger and adds the sizes.

3Hint 3Explore hint

Keep size[root] for each circle and a running best. On a real merge, best = max(best, new size). Append best after each query. Back parent/size with hash maps for the 10⁹ id space.

A · Core idea

Union-find turns whole-set merging into a single pointer change, keeping circle sizes on the roots.

find with path compression. find(x) walks parent pointers to the root and compresses the path so future lookups are near-constant.

Why hash maps. IDs reach 10⁹ and are sparse, so an array of that size is infeasible. Hash maps store only the people actually involved, with lazy singleton creation on first contact.

B · Visual dry run

Interactive dry run

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

queries = [[1,2],[3,4],[2,3]]

Array state

(1,2)

size 2, best 2

[0]

Current pointerResolved stateNot processed

Final result[2, 2, 4]

C · Code with teaching comments

solution.javaJava

Union-Find with Size (Optimal) — optimal

4 teaching notes

1
private Map<Integer, Integer> parent = new HashMap<>();
2
private Map<Integer, Integer> size = new HashMap<>();
3
 
4
private int find(int x) {
5
    // Lazily register a never-seen person as their own singleton root.
6
    parent.putIfAbsent(x, x);
7
    size.putIfAbsent(x, 1);
8
    int root = x;
9
    while (parent.get(root) != root) root = parent.get(root);
10
    // Re-point every node on the path directly to the root to flatten future finds.
11
    while (parent.get(x) != root) {        // path compression
12
        int next = parent.get(x);
13
        parent.put(x, root);
14
        x = next;
15
    }
16
    return root;
17
}
18
 
19
public int[] maxCircle(int[][] queries) {
20
    int[] result = new int[queries.length];
21
    int best = 0;
22
    for (int qi = 0; qi < queries.length; qi++) {
23
        int ra = find(queries[qi][0]);
24
        int rb = find(queries[qi][1]);
25
        if (ra != rb) {
26
            // Union by size: attach the smaller circle under the larger.
27
            if (size.get(ra) < size.get(rb)) { int t = ra; ra = rb; rb = t; }
28
            parent.put(rb, ra);             // union by size
29
            int merged = size.get(ra) + size.get(rb);
30
            size.put(ra, merged);
31
            // The only candidate for a new global max is the freshly merged circle.
32
            best = Math.max(best, merged);
33
        }
34
        result[qi] = best;
35
    }
36
    return result;
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(q · α(n)) ≈ O(q) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7duplicate query (1,2) then (1,2) — Second union finds equal roots → no-op; best unchanged but still appended.Explore edge cases

Edge cases handled

duplicate query (1,2) then (1,2)Second union finds equal roots → no-op; best unchanged but still appended.
query (5, 5) (same person)find(5) == find(5) → no merge; size stays 1, best unaffected.
all distinct pairs, no overlapsEvery circle is size 2; best is 2 after the first query and stays 2.

Pitfalls

Updating best on a no-op union (same root).
Skipping union by size and/or path compression — finds degrade toward O(n).
Using arrays for parent/size when IDs reach 10⁹.
Re-deriving the max by scanning all components each query — that's O(q·n).

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 Map<Integer, Integer> parent = new HashMap<>();
private Map<Integer, Integer> size = new HashMap<>();

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Max updated on a no-op union

If a and b are already in the same circle, nothing merges. Touching best (or re-adding size) here can overcount, and re-summing sizes corrupts the component size.

Explore the code comparison

Don't write this

ra, rb = find(a), find(b)
parent[rb] = ra            # blindly unions even if ra == rb
size[ra] += size[rb]
best = max(best, size[ra])

Write this instead

ra, rb = find(a), find(b)
if ra != rb:               # only on a real merge
    parent[rb] = ra
    size[ra] += size[rb]
    best = max(best, size[ra])

Array DSU with huge IDs

IDs reach 10⁹, so new int[10⁹] is infeasible (memory) — and even compressing requires a map. A hash-map DSU stores only the people actually seen.

Explore the code comparison

Don't write this

int[] parent = new int[1_000_000_001];   // out of memory

Write this instead

Map<Integer, Integer> parent = new HashMap<>();   // lazy, sparse

Rescanning for the max

Deriving the largest circle by iterating all components after each query is O(n) per query → O(q·n). Maintaining a running max updated on each real merge is O(1).

Explore the code comparison

Don't write this

result.append(max(size[find(p)] for p in all_people))  # O(n) per query

Write this instead

best = max(best, size[ra])   # O(1) update on merge
result.append(best)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Union-find with component sizes + running max

Code pattern to memorize

parent = {}, size = {}, best = 0
for (a, b) in queries:
    ra, rb = find(a), find(b)        # find auto-creates new singletons (size 1)
    if ra != rb:
        if size[ra] < size[rb]: swap(ra, rb)
        parent[rb] = ra
        size[ra] += size[rb]
        best = max(best, size[ra])
    append best
return results

Rules to remember

1Track a size per root and merge smaller into larger (union by size) to keep trees shallow.
2Maintain a running max circle size; update it only when a union actually merges two different circles.
3Person IDs are huge (up to 10⁹) → back parent/size with hash maps, lazily creating a singleton (size 1) on first sight.
4A query joining two people already in the same circle changes nothing — best stays the same; still append it.
5Append the current best after every query, including no-op unions.

Use this pattern when

Incremental **merging** of groups with a 'largest group so far' question
Dynamic connectivity: edges arrive online, queries interleave
Sparse / large id space where arrays won't fit → hash-map DSU
You only need group *sizes/connectivity*, not paths or distances

Choose another pattern when

Edges are *removed* over time → union-find can't undo; use other structures (or offline + reverse)
You need shortest paths or weighted distances → Dijkstra/BFS, not DSU
A static graph asked once → a single BFS/DFS pass suffices
You must enumerate each group's members repeatedly → maintain explicit lists, not just sizes

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
Same union-find; track a component counter that decrements on each real merge instead of a max size.
Accounts Merge
Coming soon
Union-find over emails to merge accounts sharing any address, then group members by root.
Number of Islands II
Coming soon
Online land additions on a grid — union neighbors and report the island count after each addition.
Kruskal (MST): Really Special Subtree
Union-find as the cycle-detection engine while greedily adding the cheapest edges.

Same pattern

←

Floyd: City of Blinding Lights

Continue · Next problem

Kruskal (MST): Really Special Subtree