Crack the Backend

Problem Statement

Each account is a list: first element is the name, the rest are emails. Two accounts belong to the same person if they share any email. Merge all accounts that belong to the same person: one account per person with name and a sorted list of all emails. Return the merged accounts (format: [name, email1, email2, ...]).

Key Observations

Union Find on emails: Treat each email as a node. Map each email to its owner name. For each account, union the first email with every other email in that account — so all emails in one account end up in the same set. Then group all emails by their root (find(email)); for each group, collect the (unique) name and sort the emails; output [name, ...sorted emails].

Approach

High-level: Map emailToName; UF over emails. For each account: for each email union with account.get(1). Group emails by find(email); for each group sort and prepend name. Return list of [name, ...emails].

Steps: Map<String,String> owner; UF with email as id. For (List<String> acc : accounts) { String name = acc.get(0); for (int i=1;i<acc.size();i++) { owner.put(acc.get(i), name); if (i>1) union(acc.get(1), acc.get(i)); } } Group by find; sort each group; build result.

Implementation

Java

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, String> owner = new HashMap<>();
    Map<String, String> parent = new HashMap<>();

    for (List<String> a : accounts) {
        String name = a.get(0);

        for (int i = 1; i < a.size(); i++) {
            owner.put(a.get(i), name);
            parent.putIfAbsent(a.get(i), a.get(i));
        }
    }

    for (List<String> a : accounts)
    for (int i = 2; i < a.size(); i++)
    union(parent, a.get(1), a.get(i));
    Map<String, TreeSet<String>> groups = new HashMap<>();

    for (String e : parent.keySet()) {
        String root = find(parent, e);
        groups.computeIfAbsent(root, x -> new TreeSet<>()).add(e);
    }

    List<List<String>> res = new ArrayList<>();

    for (Map.Entry<String, TreeSet<String>> en : groups.entrySet()) {
        List<String> row = new ArrayList<>();
        row.add(owner.get(en.getKey()));
        row.addAll(en.getValue());
        res.add(row);
    }

    return res;
}

Test Cases

Example 1

Input

accounts = [["John","j1","j2"],["John","j1","j3"]]

Expected

One John with j1,j2,j3

Explanation

Same email j1 merges.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.