Algorithm


Problem Name: 721. Accounts Merge

Problem Link: https://leetcode.com/problems/accounts-merge/

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 would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

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

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Explanation:
The first and second John's are the same person as they have the common email "johnsmith@mail.com".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], 
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Example 2:

Input: accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
Output: [["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

 

Constraints:

  • 1 <= accounts.length <= 1000
  • 2 <= accounts[i].length <= 10
  • 1 <= accounts[i][j].length <= 30
  • accounts[i][0] consists of English letters.
  • accounts[i][j] (for j > 0) is a valid email.
 

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public List();
    for (List account : accounts) {
      String firstEmail = account.get(1);
      for (int i = 2; i  <  account.size(); i++) {
        adjacencyList.computeIfAbsent(firstEmail, k -> new ArrayList<>()).add(account.get(i));
        adjacencyList.computeIfAbsent(account.get(i), k -> new ArrayList < >()).add(firstEmail);
      }
    }
    Set visited = new HashSet<>();
    List < List();
    for (List account : accounts) {
      String name = account.get(0);
      String firstEmail = account.get(1);
      if (!visited.contains(firstEmail)) {
        Stack < String> stack = new Stack<>();
        stack.push(firstEmail);
        List < String> mergedAccount = new ArrayList<>();
        mergedAccount.add(name);
        while (!stack.isEmpty()) {
          String removedEmail = stack.pop();
          visited.add(removedEmail);
          mergedAccount.add(removedEmail);
          for (String neighbor : adjacencyList.getOrDefault(removedEmail, new ArrayList < >())) {
            if (!visited.contains(neighbor)) {
              visited.add(neighbor);
              stack.push(neighbor);
            }
          }
        }
        Collections.sort(mergedAccount.subList(1, mergedAccount.size()));
        mergedAccounts.add(mergedAccount);
      }
    }
    return mergedAccounts;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

Output

x
+
cmd
[["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const accountsMerge = function (accounts) {
  const roots = new Set()
  const owner = {}
  const parent = {}
  const children = {}

  for (let account of accounts) {
    let [user, root, ...emails] = account
    let r1 = find(root)
    owner[root] = user
    children[r1] = children[r1] || [root]
    roots.add(r1)

    for (let email of emails) {
      let r2 = find(email)
      if (r2 !== r1) {
        parent[r2] = r1
        children[r1].push(...(children[r2] ? children[r2] : [email]))
        roots.delete(r2)
        delete children[r2]
      }
    }
  }

  return [...roots].map((r) => [owner[r], ...children[r].sort()])

  function find(a) {
    parent[a] = parent[a] || a
    return a === parent[a] ? a : find(parent[a])
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

Output

x
+
cmd
[["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def accountsMerge(self, accounts):
        def explore(mail, q):
            q += mail,
            visited.add(mail)
            for v in edges[mail]:
                if v not in visited: explore(v, q)
            return q
        edges, owner, visited, res = collections.defaultdict(list), {}, set(), []
        for acc in accounts:
            owner[acc[1]] = acc[0]
            for i in range(1, len(acc) - 1): 
                if acc[i] != acc[i + 1]:
                    edges[acc[i]] += acc[i + 1],
                    edges[acc[i + 1]] += acc[i],
        for acc in accounts:
            if acc[1] not in visited: res += [acc[0]] + sorted(explore(acc[1], [])),
        return res
Copy The Code & Try With Live Editor

Input

x
+
cmd
accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]

#4 Code Example with C# Programming

Code - C# Programming


using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
    public class _0721_AccountsMerge
    {
        public IList < IList();
            var emailToId = new Dictionary();

            var id = 0;
            foreach (var account in accounts)
            {
                var name = string.Empty;
                foreach (var str in account)
                {
                    if (name == string.Empty)
                    {
                        name = str;
                        continue;
                    }

                    emailToName[str] = name;
                    if (!emailToId.ContainsKey(str))
                        emailToId[str] = id++;
                    uf.Union(emailToId[account[1]], emailToId[str]);
                }
            }

            var map = new Dictionary < int, IList();
                map[index].Add(email);
            }

            return map.Values.Select(list =>
            {
                IList < string> temp = list.OrderBy(e => e, StringComparer.Ordinal).ToList();
                temp.Insert(0, emailToName[list[0]]);
                return temp;
            }).ToList();
        }

        public class UnionFind
        {
            private int[] parents;

            public UnionFind()
            {
                parents = new int[10001];
                for (int i = 0; i  <  10001; i++)
                    parents[i] = i;
            }

            public int Find(int index)
            {
                if (parents[index] != index)
                    parents[index] = Find(parents[index]);
                return parents[index];
            }

            public void Union(int index1, int index2)
            {
                parents[Find(index1)] = Find(index2);
            }
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]

Output

x
+
cmd
[["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]
Advertisements

Demonstration


Previous
#720 Leetcode Longest Word in Dictionary Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#722 Leetcode Remove Comments Solution in C, C++, Java, JavaScript, Python, C# Leetcode