Accounts Merge

84.Accounts Merge

Union-Find

Hash Table

Problem Statement:

Given a list of accounts where each account contains a name followed by emails, merge accounts if two accounts share at least one email. Return the merged accounts, each sorted lexicographically by email, with the name as the first element.

Algorithm:

1. Use Union-Find to group accounts by shared emails:
• Initialize an array to represent each account's parent in the union-find structure.
• Traverse through emails for each account. If an email is already seen, union the current account with the previously associated account.
2. Group emails for each parent account.
3. Sort the emails in each group and prepend the account name.

Complexity:

Time: O(n * log(n)), where n is the total number of emails | Space: O(n)

Java Implementation:

import java.util.*;

public class Solution {
    public List> accountsMerge(List> accounts) {
        int[] parent = new int[accounts.size()];
        
        // Initialize each account as its own parent
        for (int i = 0; i < parent.length; i++) 
            parent[i] = i;
        
        Map emailParent = new HashMap<>();
        
        for (int i = 0; i < accounts.size(); i++) {
            List emails = accounts.get(i);
            for (int j = 1; j < emails.size(); j++) {
                String email = emails.get(j);
                if (!emailParent.containsKey(email)) {
                    emailParent.put(email, i);
                } else {
                    int p1 = find(i, parent);
                    int p2 = find(emailParent.get(email), parent);
                    if (p1 != p2) union(p1, p2, parent);
                }
            }
        }
        
        // Group emails by parent
        Map> users = new HashMap<>();
        for (int i = 0; i < accounts.size(); i++) {
            int p = find(i, parent);
            List emails = accounts.get(i);
            users.putIfAbsent(p, new HashSet<>());
            users.get(p).addAll(emails.subList(1, emails.size()));
        }
                                     
        // Build the result
        List> res = new ArrayList<>();
        for (int user : users.keySet()) {
            List curr = new ArrayList<>(users.get(user));
            Collections.sort(curr);
            curr.add(0, accounts.get(user).get(0));  
            res.add(curr);
        }
        
        return res;
    }
    
    public int find(int i, int[] parent) {
        if (parent[i] == i) return i;
        parent[i] = find(parent[i], parent);
        return parent[i];
    }
    
    public void union(int x, int y, int[] parent) {
        parent[x] = y;
    }
}

Python Implementation:

from collections import defaultdict

class Solution:
    def accountsMerge(self, accounts):
        parent = list(range(len(accounts)))
        email_to_parent = {}

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            parent[find(x)] = find(y)

        for i, account in enumerate(accounts):
            for email in account[1:]:
                if email in email_to_parent:
                    union(i, email_to_parent[email])
                email_to_parent[email] = i

        users = defaultdict(set)
        for email, p in email_to_parent.items():
            users[find(p)].add(email)

        result = []
        for key, emails in users.items():
            result.append([accounts[key][0]] + sorted(emails))

        return result

C++ Implementation:

#include 
#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    vector> accountsMerge(vector>& accounts) {
        vector parent(accounts.size());
        iota(parent.begin(), parent.end(), 0);
        unordered_map emailParent;

        function find = [&](int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };

        auto unionNodes = [&](int x, int y) {
            parent[find(x)] = find(y);
        };

        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 1; j < accounts[i].size(); j++) {
                string email = accounts[i][j];
                if (emailParent.count(email)) {
                    unionNodes(i, emailParent[email]);
                }
                emailParent[email] = i;
            }
        }

        unordered_map> users;
        for (auto& [email, p] : emailParent) {
            users[find(p)].insert(email);
        }

        vector> result;
        for (auto& [user, emails] : users) {
            vector curr(emails.begin(), emails.end());
            sort(curr.begin(), curr.end());
            curr.insert(curr.begin(), accounts[user][0]);
            result.push_back(curr);
        }
        return result;
    }
};