Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-111 · FOCUSED PRACTICE

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

  1. 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.

  2. 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.

  3. Input: [[Ada,x],[Grace,x]]
    Output: IllegalArgumentException

    A shared exact email with conflicting names violates the declared identity policy.

  4. Input: [[A,X@example],[A,x@example]]
    Output: two independent rows

    Identifier 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.

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.

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.

Account identity — shared emails and final component assembly

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.

State after this step
VariableValue
input[["A","z","x"],["A","y","x"],["A"],["A","k"]]
parent[0,1,2,3]
size[1,1,1,1]
components4
processed[]
phase"initial"
currentnull
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
  1. 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
  2. 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
    email
    "z"
    previous
    null
    owners
    [{"email":"z","account":0}]
    phase
    "owner"
    current
    0
  3. 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
    email
    "x"
    previous
    null
    owners
    [{"email":"z","account":0},{"email":"x","account":0}]
    phase
    "owner"
    current
    0
  4. 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
    email
    "y"
    previous
    null
    owners
    [{"email":"z","account":0},{"email":"x","account":0},{"email":"y","account":1}]
    phase
    "owner"
    current
    1
  5. 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
    email
    "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
  6. 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
    email
    "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
  7. 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
    email
    "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
  8. 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
    email
    "k"
    previous
    null
    owners
    [{"email":"z","account":0},{"email":"x","account":0},{"email":"y","account":1},{"email":"k","account":3}]
    phase
    "owner"
    current
    3
  9. 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"
  10. 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.

Account identity — shared emails and final component assembly

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.

State after this step
VariableValue
input[["Ada","a","b"],["Ada","c","d"],["Ada","b","c"]]
parent[0,1,2]
size[1,1,1]
components3
processed[]
phase"initial"
currentnull
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
  1. 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
  2. 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
    email
    "a"
    previous
    null
    owners
    [{"email":"a","account":0}]
    phase
    "owner"
    current
    0
  3. 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
    email
    "b"
    previous
    null
    owners
    [{"email":"a","account":0},{"email":"b","account":0}]
    phase
    "owner"
    current
    0
  4. 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
    email
    "c"
    previous
    null
    owners
    [{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1}]
    phase
    "owner"
    current
    1
  5. 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
    email
    "d"
    previous
    null
    owners
    [{"email":"a","account":0},{"email":"b","account":0},{"email":"c","account":1},{"email":"d","account":1}]
    phase
    "owner"
    current
    1
  6. 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
    email
    "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
  7. 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
    email
    "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
  8. 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
    email
    "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
  9. 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
    email
    "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
  10. 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
    email
    "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
  11. 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
    email
    "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
  12. 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"
  13. 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.

Account identity — shared emails and final component assembly

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.

State after this step
VariableValue
input[["A","x","x"],["A","x"]]
parent[0,1]
size[1,1]
components2
processed[]
phase"initial"
currentnull
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
  1. 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
  2. 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
    email
    "x"
    previous
    null
    owners
    [{"email":"x","account":0}]
    phase
    "owner"
    current
    0
  3. 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
    email
    "x"
    previous
    0
    owners
    [{"email":"x","account":0}]
    phase
    "find"
    current
    0
    role
    "a"
    path
    [0]
    changes
    []
    root
    0
  4. 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
    email
    "x"
    previous
    0
    owners
    [{"email":"x","account":0}]
    phase
    "find"
    current
    0
    role
    "b"
    path
    [0]
    changes
    []
    root
    0
  5. 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
    email
    "x"
    previous
    0
    owners
    [{"email":"x","account":0}]
    phase
    "same-set"
    current
    0
    rootA
    0
    rootB
    0
    kept
    0
    attached
    null
    merged
    false
  6. 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
    email
    "x"
    previous
    0
    owners
    [{"email":"x","account":0}]
    phase
    "find"
    current
    1
    role
    "a"
    path
    [1]
    changes
    []
    root
    1
  7. 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
    email
    "x"
    previous
    0
    owners
    [{"email":"x","account":0}]
    phase
    "find"
    current
    0
    role
    "b"
    path
    [0]
    changes
    []
    root
    0
  8. 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
    email
    "x"
    previous
    0
    owners
    [{"email":"x","account":0}]
    phase
    "union"
    current
    1
    rootA
    1
    rootB
    0
    kept
    1
    attached
    0
    merged
    true
  9. 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"
  10. 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.

Account identity — shared emails and final component assembly

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.

State after this step
VariableValue
input[["Ada","x"],["Grace","x"]]
parent[0,1]
size[1,1]
components2
processed[]
phase"initial"
currentnull
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
  1. 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
  2. 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
    email
    "x"
    previous
    null
    owners
    [{"email":"x","account":0}]
    phase
    "owner"
    current
    0
  3. 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
    email
    "x"
    previous
    0
    owners
    [{"email":"x","account":0}]
    phase
    "conflict"
    current
    1
  4. 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.

Account identity — shared emails and final component assembly

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.

State after this step
VariableValue
input[["A","X@example"],["A","x@example"]]
parent[0,1]
size[1,1]
components2
processed[]
phase"initial"
currentnull
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
  1. 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
  2. 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
    email
    "X@example"
    previous
    null
    owners
    [{"email":"X@example","account":0}]
    phase
    "owner"
    current
    0
  3. 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
    email
    "x@example"
    previous
    null
    owners
    [{"email":"X@example","account":0},{"email":"x@example","account":1}]
    phase
    "owner"
    current
    1
  4. 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"
  5. 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.

Account identity — shared emails and final component assembly

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.

    State after this step
    VariableValue
    input[]
    parent[]
    size[]
    components0
    processed[]
    phase"initial"
    currentnull
    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
    1. 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
    2. 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"
    3. 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

    1. Input: Empty input and name-only rows
      Output: fresh mutable rows with no invented email links

      Equal names alone do not merge.

    2. Input: Repeated email and late bridge
      Output: one copy of each sorted email in the right component

      Transitive closure and deduplication.

    3. Input: Linked, unmodifiable, and aliased source rows
      Output: same canonical result; source unchanged

      Container access/ownership contract.

    4. Input: Conflicting shared email followed by a null field
      Output: NullPointerException

      Complete structural validation precedes semantic rejection.

    5. Input: 50,000-account overlapping-email chain
      Output: one sorted component

      Main 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.

    Related foundations

    Keep practicing

    Return to the lesson

    AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply external-platform parity or company-frequency claims.