DSA-111 · Join account records through exact shared-email ownership, then canonicalize output
Accounts Merge
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 8629 deterministic checks. Learner drafts are not executed.
Understand the problem
Merge account records connected transitively by shared email identifiers. Return one independently mutable row per merged component, with its name followed by unique sorted emails.
- accounts is a nonnull List of nonnull nonempty account rows. The first field is a nonnull nonempty name and subsequent fields are nonnull nonempty email identifiers; name-only rows are valid. Empty outer input is valid. At most 100,000 rows, 200,000 email occurrences, and 2,000,000 total UTF-16 code units are size preconditions. Null containers/fields throw NullPointerException; empty rows or fields throw IllegalArgumentException. Validate/copy the complete input before semantic conflict checks.
- Email identifiers are exact case-sensitive Strings. Do not trim, lowercase, validate address syntax, remove dots, or infer identity from equal names. Accounts sharing an email must have equal names; otherwise reject with IllegalArgumentException. Transitive chains of shared emails merge, and repeated emails within one row are one identifier. Name-only accounts stay independent even when their names match.
- Preserve the outer input, every row object, order, and original String references. Unmodifiable lists, linked lists, and aliased source rows are supported through private indexed copies. Output components follow the earliest source-account index in each component; within a row, emails use Java String.compareTo order. Return fresh mutable outer/row lists, distinct across rows/calls and separate from input containers. Immutable String objects may be shared.
Examples
Input:
[[A,z,x],[A,y,x],[A],[A,k]]
Output:[[A,x,y,z],[A],[A,k]]The first two records share x. Equal name A does not merge the independent name-only or k records.
Input:
[[Ada,a,b],[Ada,c,d],[Ada,b,c]]
Output:[[Ada,a,b,c,d]]The third record bridges two earlier groups. The final DSU root need not be source index zero.
Input:
[[Ada,x],[Grace,x]]
Output:IllegalArgumentExceptionA shared exact email with conflicting names violates the declared identity policy.
Input:
[[A,X@example],[A,x@example]]
Output:two independent rowsIdentifier matching is case-sensitive; no email-provider normalization is inferred.
Before you start
- Transitive record identity through shared identifiers
- Root grouping, exact String equality, and deterministic container ownership
Recognize the structure
Records are the DSU vertices; email Strings create connections between them. One remembered owner per distinct email is enough to join all its records as a star, avoiding an account-overlap clique. Output ordering and email deduplication are separate from arbitrary representative identities.
Try before revealing
Hint 1
Treat records as vertices and each exact shared email as a connection.
Hint 2
Remember one first owner per email, checking the declared name-consistency policy.
Hint 3
After all unions, group distinct emails by final roots and emit components by earliest source index.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Build every pairwise account-overlap edge, then traverse
After validation and private copying, compare each account pair for at least one exact shared email. Build an undirected overlap graph, BFS each component in earliest-source order, reject inconsistent component names, and collect emails in a TreeSet. This compiles and exposes the identity semantics, but pairwise comparisons and a dense overlap graph can be expensive.
Improve the baseline
Normalize container access without changing identifiers
Copy fields into private ArrayList rows using iteration, so indexed processing does not become quadratic on linked input lists. The copies contain original immutable String references and validate all fields before identity conflicts.
Map each email to its first source account
On a new email, store its account index. On repetition, check name equality and union the current record with the remembered owner. Owner indices need not be updated to roots because union calls find.
Group only after all bridges are processed
Find the final root of each distinct email owner, then scan source accounts in increasing index order. Emit each root once, using the first member’s name and sorted unique emails. This separates representative choice from the canonical component order and retains name-only rows.
Why it is correct
Forest and size invariant
Every parent chain ends at a self-parent root. Roots partition vertices into disjoint sets; only a root’s size is its current component cardinality. Nonroot size entries remain stale. Union attaches one root to another, so no parent cycle is introduced.
Shared-email graph equivalence
For one email, joining every later owner to the first owner connects exactly the records containing that identifier. The union of these stars has the same component partition as all pairwise overlap edges. Any inferred merge therefore has a chain of shared emails, and every such chain is represented.
Conflict policy and canonical assembly
Each shared-email connection enforces equal names, so all names in a valid connected component agree transitively. The owner map contains every distinct email exactly once; grouping final roots assigns each to exactly one component. The ascending source scan emits at the earliest member, while sorting removes dependence on HashMap iteration or DSU root choice.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static final class Dsu {
final int[] parent,size;int components;
Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}}
int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;}
boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;}
}
private static List<List<String>> validatedCopy(List<List<String>> accounts) {
Objects.requireNonNull(accounts,"accounts");List<List<String>> copy=new ArrayList<>();
for(List<String> account:accounts){Objects.requireNonNull(account,"account");if(account.isEmpty())throw new IllegalArgumentException("missing account name");List<String> row=new ArrayList<>();for(String field:account){Objects.requireNonNull(field,"field");if(field.isEmpty())throw new IllegalArgumentException("empty name/email");row.add(field);}copy.add(row);}return copy;
}
public static List<List<String>> mergeAccounts(List<List<String>> accounts) {
accounts=validatedCopy(accounts);int n=accounts.size();Dsu dsu=new Dsu(n);Map<String,Integer> owner=new HashMap<>();
for(int i=0;i<n;i++)for(int j=1;j<accounts.get(i).size();j++) {
String email=accounts.get(i).get(j);Integer previous=owner.putIfAbsent(email,i);
if(previous!=null){if(!accounts.get(i).get(0).equals(accounts.get(previous).get(0)))throw new IllegalArgumentException("conflicting names for shared email");dsu.union(i,previous);}
}
Map<Integer,List<String>> groups=new HashMap<>();for(var entry:owner.entrySet())groups.computeIfAbsent(dsu.find(entry.getValue()),key->new ArrayList<>()).add(entry.getKey());
boolean[] emitted=new boolean[n];List<List<String>> result=new ArrayList<>();
for(int i=0;i<n;i++){int root=dsu.find(i);if(emitted[root])continue;emitted[root]=true;List<String> emails=new ArrayList<>(groups.getOrDefault(root,List.of()));emails.sort(Comparator.naturalOrder());List<String> row=new ArrayList<>();row.add(accounts.get(i).get(0));row.addAll(emails);result.add(row);}
return result;
}
public static List<List<String>> baseline(List<List<String>> accounts) {
accounts=validatedCopy(accounts);int n=accounts.size();List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<n;i++)graph.add(new ArrayList<>());
for(int i=0;i<n;i++)for(int j=0;j<i;j++){boolean overlap=false;for(int a=1;a<accounts.get(i).size()&&!overlap;a++)for(int b=1;b<accounts.get(j).size();b++)if(accounts.get(i).get(a).equals(accounts.get(j).get(b))){overlap=true;break;}if(overlap){graph.get(i).add(j);graph.get(j).add(i);}}
boolean[] seen=new boolean[n];List<List<String>> result=new ArrayList<>();ArrayDeque<Integer> queue=new ArrayDeque<>();
for(int start=0;start<n;start++)if(!seen[start]){String name=accounts.get(start).get(0);TreeSet<String> emails=new TreeSet<>();seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();if(!name.equals(accounts.get(v).get(0)))throw new IllegalArgumentException("conflicting component names");for(int j=1;j<accounts.get(v).size();j++)emails.add(accounts.get(v).get(j));for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}List<String> row=new ArrayList<>();row.add(name);row.addAll(emails);result.add(row);}return result;
}
}
Read the meaningful blocks
Iterative path halving is not full flattening
find rewrites the current vertex to its grandparent, then jumps to that updated parent. It may skip intermediate vertices and may leave a path of length greater than one. Rewiring preserves set membership; an unsuccessful union can still compress paths.
The first owner is not a stable representative
An email can keep owner index zero even after root zero attaches elsewhere. Always find its current representative during unions/grouping. Registering the latest account’s name as an identity key would wrongly merge unrelated records.
Output structure is independent; text may be shared
Allocate new outer/row lists, including name-only rows. Strings are immutable, so sharing them is allowed. Private input copies add real O(N+K) reference storage and make linked/unmodifiable inputs safe.
Grouping is a batch, not a HashMap-order trace
Walkthroughs show exact union-pass forests. Java’s grouping calls can compress paths further in unspecified map iteration order; assembly is shown as one canonical result batch, not a fabricated exact map iteration.
Complexity
Let N be accounts, K email occurrences, D distinct emails, T total input code units, and L>=1 the maximum field length. Expected main time is O(T+N+K+(N+K)·α(N+1)+K·L+D log(D+1)·L): private copying/validation, hashing, DSU operations, repeated name comparisons, and worst-case String sorting costs. K·L explicitly covers repeated long-name equality checks that are not bounded by reading each source name once.
Auxiliary reference storage is O(N+K+D+1), including private row copies, DSU arrays, owner map and grouping lists; output uses O(N+D+1) list/field references, sharing immutable text. For A overlap adjacency occurrences, the pairwise baseline takes O(N²+K²·L+N·L+K log(D+1)·L+1) time and O(N+K+A+1) auxiliary space. A can be Θ(N²) even when a single shared email suffices for a linear-size union star. Union by size plus path halving gives inverse-Ackermann amortized operation cost over a sequence; it does not promise each individual find is constant time. A single find can still take O(log(N+1)) in a size-balanced forest. Parent links encode membership, not a path made of original graph edges.
Exact-state walkthroughs
Reveal normal and boundary traces
Shared email joins records; equal names alone do not
Input: [["A","z","x"],["A","y","x"],["A"],["A","k"]] · Merged account rows / thrown outcome: [["A","x","y","z"],["A"],["A","k"]]
Step 1 of 10: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Source accounts — row indices define DSU vertices
- 0: Aemail occurrences: z, x
- 1: Aemail occurrences: y, x
- 2: Aemail occurrences: (none)
- 3: Aemail occurrences: k
First email owner — first-seen logical order, not HashMap iteration
Empty.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
- 2parent → 2 (root)root size 1
- 3parent → 3 (root)root size 1
Component count: 4. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
- root 3: {3}
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [["A","z","x"],["A","y","x"],["A"],["A","k"]] |
| parent | [0,1,2,3] |
| size | [1,1,1,1] |
| components | 4 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static List<List<String>> validatedCopy(List<List<String>> accounts) { 10 Objects.requireNonNull(accounts,"accounts");List<List<String>> copy=new ArrayList<>(); 11 for(List<String> account:accounts){Objects.requireNonNull(account,"account");if(account.isEmpty())throw new IllegalArgumentException("missing account name");List<String> row=new ArrayList<>();for(String field:account){Objects.requireNonNull(field,"field");if(field.isEmpty())throw new IllegalArgumentException("empty name/email");row.add(field);}copy.add(row);}return copy; 12 } 13 public static List<List<String>> mergeAccounts(List<List<String>> accounts) { 14 accounts=validatedCopy(accounts);int n=accounts.size();Dsu dsu=new Dsu(n);Map<String,Integer> owner=new HashMap<>(); 15 for(int i=0;i<n;i++)for(int j=1;j<accounts.get(i).size();j++) { 16 String email=accounts.get(i).get(j);Integer previous=owner.putIfAbsent(email,i); 17 if(previous!=null){if(!accounts.get(i).get(0).equals(accounts.get(previous).get(0)))throw new IllegalArgumentException("conflicting names for shared email");dsu.union(i,previous);} 18 } 19 Map<Integer,List<String>> groups=new HashMap<>();for(var entry:owner.entrySet())groups.computeIfAbsent(dsu.find(entry.getValue()),key->new ArrayList<>()).add(entry.getKey()); 20 boolean[] emitted=new boolean[n];List<List<String>> result=new ArrayList<>(); 21 for(int i=0;i<n;i++){int root=dsu.find(i);if(emitted[root])continue;emitted[root]=true;List<String> emails=new ArrayList<>(groups.getOrDefault(root,List.of()));emails.sort(Comparator.naturalOrder());List<String> row=new ArrayList<>();row.add(accounts.get(i).get(0));row.addAll(emails);result.add(row);} 22 return result; 23 } 24 public static List<List<String>> baseline(List<List<String>> accounts) { 25 accounts=validatedCopy(accounts);int n=accounts.size();List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<n;i++)graph.add(new ArrayList<>()); 26 for(int i=0;i<n;i++)for(int j=0;j<i;j++){boolean overlap=false;for(int a=1;a<accounts.get(i).size()&&!overlap;a++)for(int b=1;b<accounts.get(j).size();b++)if(accounts.get(i).get(a).equals(accounts.get(j).get(b))){overlap=true;break;}if(overlap){graph.get(i).add(j);graph.get(j).add(i);}} 27 boolean[] seen=new boolean[n];List<List<String>> result=new ArrayList<>();ArrayDeque<Integer> queue=new ArrayDeque<>(); 28 for(int start=0;start<n;start++)if(!seen[start]){String name=accounts.get(start).get(0);TreeSet<String> emails=new TreeSet<>();seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();if(!name.equals(accounts.get(v).get(0)))throw new IllegalArgumentException("conflicting component names");for(int j=1;j<accounts.get(v).size();j++)emails.add(accounts.get(v).get(j));for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}List<String> row=new ArrayList<>();row.add(name);row.addAll(emails);result.add(row);}return result; 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- phase
"initial"- current
null
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- account
0- column
1"z"- previous
null- owners
[{"email":"z","account":0}]- phase
"owner"- current
0
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- account
0- column
2"x"- previous
null- owners
[{"email":"z","account":0},{"email":"x","account":0}]- phase
"owner"- current
0
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- account
1- column
1"y"- previous
null- owners
[{"email":"z","account":0},{"email":"x","account":0},{"email":"y","account":1}]- phase
"owner"- current
1
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- account
1- column
2"x"- previous
0- owners
[{"email":"z","account":0},{"email":"x","account":0},{"email":"y","account":1}]- phase
"find"- current
1- role
"a"- path
[1]- changes
[]- root
1
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- account
1- column
2"x"- previous
0- owners
[{"email":"z","account":0},{"email":"x","account":0},{"email":"y","account":1}]- phase
"find"- current
0- role
"b"- path
[0]- changes
[]- root
0
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- parent
[1,1,2,3]- size
[1,2,1,1]- components
3- processed
[{"a":1,"b":0,"merged":true}]- account
1- column
2"x"- previous
0- owners
[{"email":"z","account":0},{"email":"x","account":0},{"email":"y","account":1}]- phase
"union"- current
1- rootA
1- rootB
0- kept
1- attached
0- merged
true
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- parent
[1,1,2,3]- size
[1,2,1,1]- components
3- processed
[{"a":1,"b":0,"merged":true}]- account
3- column
1"k"- previous
null- owners
[{"email":"z","account":0},{"email":"x","account":0},{"email":"y","account":1},{"email":"k","account":3}]- phase
"owner"- current
3
- Assemble independent output rows by earliest source-account position.
Emails are unique and sorted by Java String order. Grouping is shown as one batch: Java HashMap iteration is unspecified and its find calls may compress paths further. The union-pass forest is not presented as final grouping storage.
- input
[["A","z","x"],["A","y","x"],["A"],["A","k"]]- rows
[["A","x","y","z"],["A"],["A","k"]]- phase
"assembled"
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[["A","x","y","z"],["A"],["A","k"]]
A late bridge merges two existing components
Input: [["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]] · Merged account rows / thrown outcome: [["Ada","a","b","c","d"]]
Step 1 of 13: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Source accounts — row indices define DSU vertices
- 0: Adaemail occurrences: a, b
- 1: Adaemail occurrences: c, d
- 2: Adaemail occurrences: b, c
First email owner — first-seen logical order, not HashMap iteration
Empty.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
- 2parent → 2 (root)root size 1
Component count: 3. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]] |
| parent | [0,1,2] |
| size | [1,1,1] |
| components | 3 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static List<List<String>> validatedCopy(List<List<String>> accounts) { 10 Objects.requireNonNull(accounts,"accounts");List<List<String>> copy=new ArrayList<>(); 11 for(List<String> account:accounts){Objects.requireNonNull(account,"account");if(account.isEmpty())throw new IllegalArgumentException("missing account name");List<String> row=new ArrayList<>();for(String field:account){Objects.requireNonNull(field,"field");if(field.isEmpty())throw new IllegalArgumentException("empty name/email");row.add(field);}copy.add(row);}return copy; 12 } 13 public static List<List<String>> mergeAccounts(List<List<String>> accounts) { 14 accounts=validatedCopy(accounts);int n=accounts.size();Dsu dsu=new Dsu(n);Map<String,Integer> owner=new HashMap<>(); 15 for(int i=0;i<n;i++)for(int j=1;j<accounts.get(i).size();j++) { 16 String email=accounts.get(i).get(j);Integer previous=owner.putIfAbsent(email,i); 17 if(previous!=null){if(!accounts.get(i).get(0).equals(accounts.get(previous).get(0)))throw new IllegalArgumentException("conflicting names for shared email");dsu.union(i,previous);} 18 } 19 Map<Integer,List<String>> groups=new HashMap<>();for(var entry:owner.entrySet())groups.computeIfAbsent(dsu.find(entry.getValue()),key->new ArrayList<>()).add(entry.getKey()); 20 boolean[] emitted=new boolean[n];List<List<String>> result=new ArrayList<>(); 21 for(int i=0;i<n;i++){int root=dsu.find(i);if(emitted[root])continue;emitted[root]=true;List<String> emails=new ArrayList<>(groups.getOrDefault(root,List.of()));emails.sort(Comparator.naturalOrder());List<String> row=new ArrayList<>();row.add(accounts.get(i).get(0));row.addAll(emails);result.add(row);} 22 return result; 23 } 24 public static List<List<String>> baseline(List<List<String>> accounts) { 25 accounts=validatedCopy(accounts);int n=accounts.size();List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<n;i++)graph.add(new ArrayList<>()); 26 for(int i=0;i<n;i++)for(int j=0;j<i;j++){boolean overlap=false;for(int a=1;a<accounts.get(i).size()&&!overlap;a++)for(int b=1;b<accounts.get(j).size();b++)if(accounts.get(i).get(a).equals(accounts.get(j).get(b))){overlap=true;break;}if(overlap){graph.get(i).add(j);graph.get(j).add(i);}} 27 boolean[] seen=new boolean[n];List<List<String>> result=new ArrayList<>();ArrayDeque<Integer> queue=new ArrayDeque<>(); 28 for(int start=0;start<n;start++)if(!seen[start]){String name=accounts.get(start).get(0);TreeSet<String> emails=new TreeSet<>();seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();if(!name.equals(accounts.get(v).get(0)))throw new IllegalArgumentException("conflicting component names");for(int j=1;j<accounts.get(v).size();j++)emails.add(accounts.get(v).get(j));for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}List<String> row=new ArrayList<>();row.add(name);row.addAll(emails);result.add(row);}return result; 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- phase
"initial"- current
null
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- account
0- column
1"a"- previous
null- owners
[{"email":"a","account":0}]- phase
"owner"- current
0
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- account
0- column
2"b"- previous
null- owners
[{"email":"a","account":0},{"email":"b","account":0}]- phase
"owner"- current
0
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- account
1- column
1"c"- previous
null- owners
[{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1}]- phase
"owner"- current
1
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- account
1- column
2"d"- previous
null- owners
[{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1},{"email":"d","account":1}]- phase
"owner"- current
1
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- account
2- column
1"b"- previous
0- owners
[{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1},{"email":"d","account":1}]- phase
"find"- current
2- role
"a"- path
[2]- changes
[]- root
2
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- account
2- column
1"b"- previous
0- owners
[{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1},{"email":"d","account":1}]- phase
"find"- current
0- role
"b"- path
[0]- changes
[]- root
0
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[2,1,2]- size
[1,1,2]- components
2- processed
[{"a":2,"b":0,"merged":true}]- account
2- column
1"b"- previous
0- owners
[{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1},{"email":"d","account":1}]- phase
"union"- current
2- rootA
2- rootB
0- kept
2- attached
0- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[2,1,2]- size
[1,1,2]- components
2- processed
[{"a":2,"b":0,"merged":true}]- account
2- column
2"c"- previous
1- owners
[{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1},{"email":"d","account":1}]- phase
"find"- current
2- role
"a"- path
[2]- changes
[]- root
2
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[2,1,2]- size
[1,1,2]- components
2- processed
[{"a":2,"b":0,"merged":true}]- account
2- column
2"c"- previous
1- owners
[{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1},{"email":"d","account":1}]- phase
"find"- current
1- role
"b"- path
[1]- changes
[]- root
1
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- parent
[2,2,2]- size
[1,1,3]- components
1- processed
[{"a":2,"b":0,"merged":true},{"a":2,"b":1,"merged":true}]- account
2- column
2"c"- previous
1- owners
[{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1},{"email":"d","account":1}]- phase
"union"- current
2- rootA
2- rootB
1- kept
2- attached
1- merged
true
- Assemble independent output rows by earliest source-account position.
Emails are unique and sorted by Java String order. Grouping is shown as one batch: Java HashMap iteration is unspecified and its find calls may compress paths further. The union-pass forest is not presented as final grouping storage.
- input
[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]- rows
[["Ada","a","b","c","d"]]- phase
"assembled"
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[["Ada","a","b","c","d"]]
Duplicate occurrences within one record
Input: [["A","x","x"],["A","x"]] · Merged account rows / thrown outcome: [["A","x"]]
Step 1 of 10: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Source accounts — row indices define DSU vertices
- 0: Aemail occurrences: x, x
- 1: Aemail occurrences: x
First email owner — first-seen logical order, not HashMap iteration
Empty.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
Component count: 2. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [["A","x","x"],["A","x"]] |
| parent | [0,1] |
| size | [1,1] |
| components | 2 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static List<List<String>> validatedCopy(List<List<String>> accounts) { 10 Objects.requireNonNull(accounts,"accounts");List<List<String>> copy=new ArrayList<>(); 11 for(List<String> account:accounts){Objects.requireNonNull(account,"account");if(account.isEmpty())throw new IllegalArgumentException("missing account name");List<String> row=new ArrayList<>();for(String field:account){Objects.requireNonNull(field,"field");if(field.isEmpty())throw new IllegalArgumentException("empty name/email");row.add(field);}copy.add(row);}return copy; 12 } 13 public static List<List<String>> mergeAccounts(List<List<String>> accounts) { 14 accounts=validatedCopy(accounts);int n=accounts.size();Dsu dsu=new Dsu(n);Map<String,Integer> owner=new HashMap<>(); 15 for(int i=0;i<n;i++)for(int j=1;j<accounts.get(i).size();j++) { 16 String email=accounts.get(i).get(j);Integer previous=owner.putIfAbsent(email,i); 17 if(previous!=null){if(!accounts.get(i).get(0).equals(accounts.get(previous).get(0)))throw new IllegalArgumentException("conflicting names for shared email");dsu.union(i,previous);} 18 } 19 Map<Integer,List<String>> groups=new HashMap<>();for(var entry:owner.entrySet())groups.computeIfAbsent(dsu.find(entry.getValue()),key->new ArrayList<>()).add(entry.getKey()); 20 boolean[] emitted=new boolean[n];List<List<String>> result=new ArrayList<>(); 21 for(int i=0;i<n;i++){int root=dsu.find(i);if(emitted[root])continue;emitted[root]=true;List<String> emails=new ArrayList<>(groups.getOrDefault(root,List.of()));emails.sort(Comparator.naturalOrder());List<String> row=new ArrayList<>();row.add(accounts.get(i).get(0));row.addAll(emails);result.add(row);} 22 return result; 23 } 24 public static List<List<String>> baseline(List<List<String>> accounts) { 25 accounts=validatedCopy(accounts);int n=accounts.size();List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<n;i++)graph.add(new ArrayList<>()); 26 for(int i=0;i<n;i++)for(int j=0;j<i;j++){boolean overlap=false;for(int a=1;a<accounts.get(i).size()&&!overlap;a++)for(int b=1;b<accounts.get(j).size();b++)if(accounts.get(i).get(a).equals(accounts.get(j).get(b))){overlap=true;break;}if(overlap){graph.get(i).add(j);graph.get(j).add(i);}} 27 boolean[] seen=new boolean[n];List<List<String>> result=new ArrayList<>();ArrayDeque<Integer> queue=new ArrayDeque<>(); 28 for(int start=0;start<n;start++)if(!seen[start]){String name=accounts.get(start).get(0);TreeSet<String> emails=new TreeSet<>();seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();if(!name.equals(accounts.get(v).get(0)))throw new IllegalArgumentException("conflicting component names");for(int j=1;j<accounts.get(v).size();j++)emails.add(accounts.get(v).get(j));for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}List<String> row=new ArrayList<>();row.add(name);row.addAll(emails);result.add(row);}return result; 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[["A","x","x"],["A","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- phase
"initial"- current
null
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["A","x","x"],["A","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- account
0- column
1"x"- previous
null- owners
[{"email":"x","account":0}]- phase
"owner"- current
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["A","x","x"],["A","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- account
0- column
2"x"- previous
0- owners
[{"email":"x","account":0}]- phase
"find"- current
0- role
"a"- path
[0]- changes
[]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["A","x","x"],["A","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- account
0- column
2"x"- previous
0- owners
[{"email":"x","account":0}]- phase
"find"- current
0- role
"b"- path
[0]- changes
[]- root
0
- The endpoints already belong to the same component.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[["A","x","x"],["A","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[{"a":0,"b":0,"merged":false}]- account
0- column
2"x"- previous
0- owners
[{"email":"x","account":0}]- phase
"same-set"- current
0- rootA
0- rootB
0- kept
0- attached
null- merged
false
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["A","x","x"],["A","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[{"a":0,"b":0,"merged":false}]- account
1- column
1"x"- previous
0- owners
[{"email":"x","account":0}]- phase
"find"- current
1- role
"a"- path
[1]- changes
[]- root
1
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[["A","x","x"],["A","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[{"a":0,"b":0,"merged":false}]- account
1- column
1"x"- previous
0- owners
[{"email":"x","account":0}]- phase
"find"- current
0- role
"b"- path
[0]- changes
[]- root
0
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[["A","x","x"],["A","x"]]- parent
[1,1]- size
[1,2]- components
1- processed
[{"a":0,"b":0,"merged":false},{"a":1,"b":0,"merged":true}]- account
1- column
1"x"- previous
0- owners
[{"email":"x","account":0}]- phase
"union"- current
1- rootA
1- rootB
0- kept
1- attached
0- merged
true
- Assemble independent output rows by earliest source-account position.
Emails are unique and sorted by Java String order. Grouping is shown as one batch: Java HashMap iteration is unspecified and its find calls may compress paths further. The union-pass forest is not presented as final grouping storage.
- input
[["A","x","x"],["A","x"]]- rows
[["A","x"]]- phase
"assembled"
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[["A","x"]]
Conflicting names reject shared identity
Input: [["Ada","x"],["Grace","x"]] · Merged account rows / thrown outcome: {"error":"IllegalArgumentException"}
Step 1 of 4: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Source accounts — row indices define DSU vertices
- 0: Adaemail occurrences: x
- 1: Graceemail occurrences: x
First email owner — first-seen logical order, not HashMap iteration
Empty.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
Component count: 2. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [["Ada","x"],["Grace","x"]] |
| parent | [0,1] |
| size | [1,1] |
| components | 2 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static List<List<String>> validatedCopy(List<List<String>> accounts) { 10 Objects.requireNonNull(accounts,"accounts");List<List<String>> copy=new ArrayList<>(); 11 for(List<String> account:accounts){Objects.requireNonNull(account,"account");if(account.isEmpty())throw new IllegalArgumentException("missing account name");List<String> row=new ArrayList<>();for(String field:account){Objects.requireNonNull(field,"field");if(field.isEmpty())throw new IllegalArgumentException("empty name/email");row.add(field);}copy.add(row);}return copy; 12 } 13 public static List<List<String>> mergeAccounts(List<List<String>> accounts) { 14 accounts=validatedCopy(accounts);int n=accounts.size();Dsu dsu=new Dsu(n);Map<String,Integer> owner=new HashMap<>(); 15 for(int i=0;i<n;i++)for(int j=1;j<accounts.get(i).size();j++) { 16 String email=accounts.get(i).get(j);Integer previous=owner.putIfAbsent(email,i); 17 if(previous!=null){if(!accounts.get(i).get(0).equals(accounts.get(previous).get(0)))throw new IllegalArgumentException("conflicting names for shared email");dsu.union(i,previous);} 18 } 19 Map<Integer,List<String>> groups=new HashMap<>();for(var entry:owner.entrySet())groups.computeIfAbsent(dsu.find(entry.getValue()),key->new ArrayList<>()).add(entry.getKey()); 20 boolean[] emitted=new boolean[n];List<List<String>> result=new ArrayList<>(); 21 for(int i=0;i<n;i++){int root=dsu.find(i);if(emitted[root])continue;emitted[root]=true;List<String> emails=new ArrayList<>(groups.getOrDefault(root,List.of()));emails.sort(Comparator.naturalOrder());List<String> row=new ArrayList<>();row.add(accounts.get(i).get(0));row.addAll(emails);result.add(row);} 22 return result; 23 } 24 public static List<List<String>> baseline(List<List<String>> accounts) { 25 accounts=validatedCopy(accounts);int n=accounts.size();List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<n;i++)graph.add(new ArrayList<>()); 26 for(int i=0;i<n;i++)for(int j=0;j<i;j++){boolean overlap=false;for(int a=1;a<accounts.get(i).size()&&!overlap;a++)for(int b=1;b<accounts.get(j).size();b++)if(accounts.get(i).get(a).equals(accounts.get(j).get(b))){overlap=true;break;}if(overlap){graph.get(i).add(j);graph.get(j).add(i);}} 27 boolean[] seen=new boolean[n];List<List<String>> result=new ArrayList<>();ArrayDeque<Integer> queue=new ArrayDeque<>(); 28 for(int start=0;start<n;start++)if(!seen[start]){String name=accounts.get(start).get(0);TreeSet<String> emails=new TreeSet<>();seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();if(!name.equals(accounts.get(v).get(0)))throw new IllegalArgumentException("conflicting component names");for(int j=1;j<accounts.get(v).size();j++)emails.add(accounts.get(v).get(j));for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}List<String> row=new ArrayList<>();row.add(name);row.addAll(emails);result.add(row);}return result; 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[["Ada","x"],["Grace","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- phase
"initial"- current
null
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["Ada","x"],["Grace","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- account
0- column
1"x"- previous
null- owners
[{"email":"x","account":0}]- phase
"owner"- current
0
- Reject inconsistent names attached to a shared email.
All input shapes and fields were validated/copied first. The input is read-only; partial private unions are discarded on this semantic error.
- input
[["Ada","x"],["Grace","x"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- account
1- column
1"x"- previous
0- owners
[{"email":"x","account":0}]- phase
"conflict"- current
1
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
{"error":"IllegalArgumentException"}
Case-sensitive identifiers remain distinct
Input: [["A","X@example"],["A","x@example"]] · Merged account rows / thrown outcome: [["A","X@example"],["A","x@example"]]
Step 1 of 5: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Source accounts — row indices define DSU vertices
- 0: Aemail occurrences: X@example
- 1: Aemail occurrences: x@example
First email owner — first-seen logical order, not HashMap iteration
Empty.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
Component count: 2. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [["A","X@example"],["A","x@example"]] |
| parent | [0,1] |
| size | [1,1] |
| components | 2 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static List<List<String>> validatedCopy(List<List<String>> accounts) { 10 Objects.requireNonNull(accounts,"accounts");List<List<String>> copy=new ArrayList<>(); 11 for(List<String> account:accounts){Objects.requireNonNull(account,"account");if(account.isEmpty())throw new IllegalArgumentException("missing account name");List<String> row=new ArrayList<>();for(String field:account){Objects.requireNonNull(field,"field");if(field.isEmpty())throw new IllegalArgumentException("empty name/email");row.add(field);}copy.add(row);}return copy; 12 } 13 public static List<List<String>> mergeAccounts(List<List<String>> accounts) { 14 accounts=validatedCopy(accounts);int n=accounts.size();Dsu dsu=new Dsu(n);Map<String,Integer> owner=new HashMap<>(); 15 for(int i=0;i<n;i++)for(int j=1;j<accounts.get(i).size();j++) { 16 String email=accounts.get(i).get(j);Integer previous=owner.putIfAbsent(email,i); 17 if(previous!=null){if(!accounts.get(i).get(0).equals(accounts.get(previous).get(0)))throw new IllegalArgumentException("conflicting names for shared email");dsu.union(i,previous);} 18 } 19 Map<Integer,List<String>> groups=new HashMap<>();for(var entry:owner.entrySet())groups.computeIfAbsent(dsu.find(entry.getValue()),key->new ArrayList<>()).add(entry.getKey()); 20 boolean[] emitted=new boolean[n];List<List<String>> result=new ArrayList<>(); 21 for(int i=0;i<n;i++){int root=dsu.find(i);if(emitted[root])continue;emitted[root]=true;List<String> emails=new ArrayList<>(groups.getOrDefault(root,List.of()));emails.sort(Comparator.naturalOrder());List<String> row=new ArrayList<>();row.add(accounts.get(i).get(0));row.addAll(emails);result.add(row);} 22 return result; 23 } 24 public static List<List<String>> baseline(List<List<String>> accounts) { 25 accounts=validatedCopy(accounts);int n=accounts.size();List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<n;i++)graph.add(new ArrayList<>()); 26 for(int i=0;i<n;i++)for(int j=0;j<i;j++){boolean overlap=false;for(int a=1;a<accounts.get(i).size()&&!overlap;a++)for(int b=1;b<accounts.get(j).size();b++)if(accounts.get(i).get(a).equals(accounts.get(j).get(b))){overlap=true;break;}if(overlap){graph.get(i).add(j);graph.get(j).add(i);}} 27 boolean[] seen=new boolean[n];List<List<String>> result=new ArrayList<>();ArrayDeque<Integer> queue=new ArrayDeque<>(); 28 for(int start=0;start<n;start++)if(!seen[start]){String name=accounts.get(start).get(0);TreeSet<String> emails=new TreeSet<>();seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();if(!name.equals(accounts.get(v).get(0)))throw new IllegalArgumentException("conflicting component names");for(int j=1;j<accounts.get(v).size();j++)emails.add(accounts.get(v).get(j));for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}List<String> row=new ArrayList<>();row.add(name);row.addAll(emails);result.add(row);}return result; 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[["A","X@example"],["A","x@example"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- phase
"initial"- current
null
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["A","X@example"],["A","x@example"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- account
0- column
1"X@example"- previous
null- owners
[{"email":"X@example","account":0}]- phase
"owner"- current
0
- Remember the first source account for this exact email.
Email keys are exact case-sensitive Strings. Equal account names alone do not establish identity. First-owner indices stay valid even when their DSU root later changes.
- input
[["A","X@example"],["A","x@example"]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- account
1- column
1"x@example"- previous
null- owners
[{"email":"X@example","account":0},{"email":"x@example","account":1}]- phase
"owner"- current
1
- Assemble independent output rows by earliest source-account position.
Emails are unique and sorted by Java String order. Grouping is shown as one batch: Java HashMap iteration is unspecified and its find calls may compress paths further. The union-pass forest is not presented as final grouping storage.
- input
[["A","X@example"],["A","x@example"]]- rows
[["A","X@example"],["A","x@example"]]- phase
"assembled"
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[["A","X@example"],["A","x@example"]]
Empty account collection
Input: [] · Merged account rows / thrown outcome: []
Step 1 of 3: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Source accounts — row indices define DSU vertices
First email owner — first-seen logical order, not HashMap iteration
Empty.
Parent forest — arrows are implementation links, not original graph edges
No vertices.
Component count: 0. Root choices need not be the smallest member.
Current partition — members grouped by representative
Empty.
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [] |
| parent | [] |
| size | [] |
| components | 0 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static List<List<String>> validatedCopy(List<List<String>> accounts) { 10 Objects.requireNonNull(accounts,"accounts");List<List<String>> copy=new ArrayList<>(); 11 for(List<String> account:accounts){Objects.requireNonNull(account,"account");if(account.isEmpty())throw new IllegalArgumentException("missing account name");List<String> row=new ArrayList<>();for(String field:account){Objects.requireNonNull(field,"field");if(field.isEmpty())throw new IllegalArgumentException("empty name/email");row.add(field);}copy.add(row);}return copy; 12 } 13 public static List<List<String>> mergeAccounts(List<List<String>> accounts) { 14 accounts=validatedCopy(accounts);int n=accounts.size();Dsu dsu=new Dsu(n);Map<String,Integer> owner=new HashMap<>(); 15 for(int i=0;i<n;i++)for(int j=1;j<accounts.get(i).size();j++) { 16 String email=accounts.get(i).get(j);Integer previous=owner.putIfAbsent(email,i); 17 if(previous!=null){if(!accounts.get(i).get(0).equals(accounts.get(previous).get(0)))throw new IllegalArgumentException("conflicting names for shared email");dsu.union(i,previous);} 18 } 19 Map<Integer,List<String>> groups=new HashMap<>();for(var entry:owner.entrySet())groups.computeIfAbsent(dsu.find(entry.getValue()),key->new ArrayList<>()).add(entry.getKey()); 20 boolean[] emitted=new boolean[n];List<List<String>> result=new ArrayList<>(); 21 for(int i=0;i<n;i++){int root=dsu.find(i);if(emitted[root])continue;emitted[root]=true;List<String> emails=new ArrayList<>(groups.getOrDefault(root,List.of()));emails.sort(Comparator.naturalOrder());List<String> row=new ArrayList<>();row.add(accounts.get(i).get(0));row.addAll(emails);result.add(row);} 22 return result; 23 } 24 public static List<List<String>> baseline(List<List<String>> accounts) { 25 accounts=validatedCopy(accounts);int n=accounts.size();List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<n;i++)graph.add(new ArrayList<>()); 26 for(int i=0;i<n;i++)for(int j=0;j<i;j++){boolean overlap=false;for(int a=1;a<accounts.get(i).size()&&!overlap;a++)for(int b=1;b<accounts.get(j).size();b++)if(accounts.get(i).get(a).equals(accounts.get(j).get(b))){overlap=true;break;}if(overlap){graph.get(i).add(j);graph.get(j).add(i);}} 27 boolean[] seen=new boolean[n];List<List<String>> result=new ArrayList<>();ArrayDeque<Integer> queue=new ArrayDeque<>(); 28 for(int start=0;start<n;start++)if(!seen[start]){String name=accounts.get(start).get(0);TreeSet<String> emails=new TreeSet<>();seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();if(!name.equals(accounts.get(v).get(0)))throw new IllegalArgumentException("conflicting component names");for(int j=1;j<accounts.get(v).size();j++)emails.add(accounts.get(v).get(j));for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}List<String> row=new ArrayList<>();row.add(name);row.addAll(emails);result.add(row);}return result; 29 } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[]- parent
[]- size
[]- components
0- processed
[]- phase
"initial"- current
null
- Assemble independent output rows by earliest source-account position.
Emails are unique and sorted by Java String order. Grouping is shown as one batch: Java HashMap iteration is unspecified and its find calls may compress paths further. The union-pass forest is not presented as final grouping storage.
- input
[]- rows
[]- phase
"assembled"
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[]
Test the contract
Input:
Empty input and name-only rows
Output:fresh mutable rows with no invented email linksEqual names alone do not merge.
Input:
Repeated email and late bridge
Output:one copy of each sorted email in the right componentTransitive closure and deduplication.
Input:
Linked, unmodifiable, and aliased source rows
Output:same canonical result; source unchangedContainer access/ownership contract.
Input:
Conflicting shared email followed by a null field
Output:NullPointerExceptionComplete structural validation precedes semantic rejection.
Input:
50,000-account overlapping-email chain
Output:one sorted componentMain implementation avoids pairwise overlap storage and recursion.
Common mistakes and counterexamples
Merge by account name
Counterexample: Two A records with unrelated identifiers are not necessarily one person.
Use exact shared emails as the only connection evidence.
Group before processing a late bridge
Counterexample: [a,b], [c,d], then [b,c] must become one component.
Finish every union before final grouping.
Assume the DSU root is the first record
Counterexample: Equal-size ties can retain the current record’s larger index.
Choose output order with an ascending source scan and an emitted-root set/flag.
Normalize addresses without an explicit identity policy
Counterexample: X@example and x@example are distinct under this contract.
Use exact Strings and treat conflicting names explicitly.
Ignore List access and text costs
Counterexample: Repeated indexed access on linked lists or repeated long-name comparisons can exceed a claimed linear bound.
Make private indexed copies and include character comparison costs.
Follow-ups
Allow different names within one identity component.
Replace rejection with an explicit canonical-name or conflict-reporting policy. Choose it from verified source provenance rather than silently taking an arbitrary DSU root’s name.
Merge multiple identity types.
Namespace identifiers such as email, phone, and external customer ID before matching. Define which evidence is sufficient, how conflicts are recorded, and which normalization is justified for each type.
Support incremental updates and deletion.
An insertion-only DSU can merge new evidence but cannot undo a mistaken connection. Preserve provenance/evidence edges and consider rebuilds, offline rollback, or a different dynamic identity model for removals.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 197/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.