algoadvance

Leetcode 721. Accounts Merge

Problem Statement

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we want to merge these accounts if two accounts have at least one common email. After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example

Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], 
            ["John", "johnnybravo@mail.com"], 
            ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
            ["Mary", "mary@mail.com"]]

Output: 
[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], 
 ["John", "johnnybravo@mail.com"], 
 ["Mary", "mary@mail.com"]]

Clarifying Questions

  1. Can two accounts have the same name but no common emails?
    • Yes, the accounts should only be merged if they share at least one email.
  2. Should the email addresses in the merged list be unique and sorted?
    • Yes, the emails should be deduplicated and sorted within each account.
  3. Can there be multiple accounts with the exact same set of emails and name?
    • No, merging will ensure that each set of emails is unique.

Strategy

  1. Use Union-Find (Disjoint Set Union) to group accounts by emails:
    • We’ll treat each email address as a node in a graph.
    • If two emails belong to the same account, there will be an edge between them.
    • We’ll use the union-find data structure to find and union emails.
  2. Mapping to Names:
    • Maintain a map email_to_name to associate each email to its corresponding name.
  3. Union-Find Operations:
    • For each account, union all its emails.
    • After processing all accounts, group all emails belonging to the same root.
  4. Result Compilation:
    • For each group of emails found with the same root, sort the emails and add the corresponding name.

Code

import java.util.*;

public class AccountsMerge {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap<>();
        Map<String, String> parent = new HashMap<>();
        
        // Initialize union-find for each email
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                emailToName.put(account.get(i), name);
                parent.put(account.get(i), account.get(i));
            }
        }
        
        // Union all emails in the same account
        for (List<String> account : accounts) {
            String firstEmail = account.get(1);
            for (int i = 2; i < account.size(); i++) {
                union(parent, firstEmail, account.get(i));
            }
        }
        
        // Find all emails belonging to the same group
        Map<String, List<String>> unions = new HashMap<>();
        for (String email : parent.keySet()) {
            String root = find(parent, email);
            unions.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
        }
        
        // Prepare the result
        List<List<String>> result = new ArrayList<>();
        for (List<String> group : unions.values()) {
            Collections.sort(group);
            group.add(0, emailToName.get(group.get(0)));
            result.add(group);
        }
        
        return result;
    }
    
    private void union(Map<String, String> parent, String email1, String email2) {
        String root1 = find(parent, email1);
        String root2 = find(parent, email2);
        if (!root1.equals(root2)) {
            parent.put(root1, root2);
        }
    }
    
    private String find(Map<String, String> parent, String email) {
        if (!email.equals(parent.get(email))) {
            parent.put(email, find(parent, parent.get(email)));
        }
        return parent.get(email);
    }

    public static void main(String[] args) {
        AccountsMerge obj = new AccountsMerge();
        
        List<List<String>> accounts = Arrays.asList(
            Arrays.asList("John", "johnsmith@mail.com", "john00@mail.com"),
            Arrays.asList("John", "johnnybravo@mail.com"),
            Arrays.asList("John", "johnsmith@mail.com", "john_newyork@mail.com"),
            Arrays.asList("Mary", "mary@mail.com")
        );
        
        System.out.println(obj.accountsMerge(accounts));
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI