Python Simple DFS with explanation!!!


  • 14

    We give each account an ID, based on the index of it within the list of accounts.

    [
    ["John", "johnsmith@mail.com", "john00@mail.com"], # Account 0
    ["John", "johnnybravo@mail.com"], # Account 1
    ["John", "johnsmith@mail.com", "john_newyork@mail.com"],  # Account 2
    ["Mary", "mary@mail.com"] # Account 3
    ]
    

    Next, build an emails_accounts_map that maps an email to a list of accounts, which can be used to track which email is linked to which account. This is essentially our graph.

    # emails_accounts_map of email to account ID
    {
      "johnsmith@mail.com": [0, 2],
      "john00@mail.com": [0],
      "johnnybravo@mail.com": [1],
      "john_newyork@mail.com": [2],
      "mary@mail.com": [3]
    }
    

    Next we do a DFS on each account in accounts list and look up emails_accounts_map to tell us which accounts are linked to that particular account via common emails. This will make sure we visit each account only once. This is a recursive process and we should collect all the emails that we encounter along the way.

    Lastly, sort the collected emails and add it to final results, res along with the name.

    - Yangshun

    class Solution(object):
        def accountsMerge(self, accounts):
            from collections import defaultdict
            visited_accounts = [False] * len(accounts)
            emails_accounts_map = defaultdict(list)
            res = []
            # Build up the graph.
            for i, account in enumerate(accounts):
                for j in range(1, len(account)):
                    email = account[j]
                    emails_accounts_map[email].append(i)
            # DFS code for traversing accounts.
            def dfs(i, emails):
                if visited_accounts[i]:
                    return
                visited_accounts[i] = True
                for j in range(1, len(accounts[i])):
                    email = accounts[i][j]
                    emails.add(email)
                    for neighbor in emails_accounts_map[email]:
                        dfs(neighbor, emails)
            # Perform DFS for accounts and add to results.
            for i, account in enumerate(accounts):
                if visited_accounts[i]:
                    continue
                name, emails = account[0], set()
                dfs(i, emails)
                res.append([name] + sorted(emails))
            return res
    

  • 0
    N

    Hello, thank you for solution

    Can you please explain how you came up with this idea? How to decide when we have to use trees and DFS? What's the chain of thought is leading to this?
    Also, can you please provide big-o analysis of the solution?


  • 4
    X

    My Java solution based on your idea. Thank you!

    class Solution {
        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            Map<String, List<Integer>> names = new HashMap<>(); // map email to names using indexes
            for (int i = 0; i < accounts.size(); i++) {
                List<String> data = accounts.get(i);
                for (int j = 1; j < data.size(); j++) {
                    String email = data.get(j);
                    List<Integer> list = names.get(email);
                    if (list == null) {
                        list = new ArrayList<Integer>();
                        names.put(email, list);
                    }
                    list.add(i);
                }
            }
            boolean[] visited = new boolean[accounts.size()];
            List<List<String>> res = new LinkedList<>();
            for (int i = 0; i < accounts.size(); i++) {
                Set<String> set = new TreeSet<String>();
                dfs(i, accounts, names, visited, set);
                if (!set.isEmpty()) {
                    List<String> list = new LinkedList<String>(set);
                    list.add(0, accounts.get(i).get(0));
                    res.add(list);
                }
            }
            return res;
        }
        private void dfs(int cur, List<List<String>> accounts, Map<String, List<Integer>> names, 
                         boolean[] visited, Set<String> set) {
            if (visited[cur]) {
                return;
            }
            visited[cur] = true;
            for (int i = 1; i < accounts.get(cur).size(); i++) {
                String email = accounts.get(cur).get(i);
                set.add(email);
                for (int index : names.get(email)) {
                    dfs(index, accounts, names, visited, set);
                }
            }
        }
    }
    

  • 0
    M

    @yangshun Hi, thank you for this concise solution.
    Question:
    Why store the account name when build up the graph?
    My solution about building:

         for i, account in enumerate(accounts):
            emails = account[1:]
            for email in emails:
                email_accounts_map[email].append(i)

  • 1

    @Miksztowi I don't store the account name when building up the graph. The graph is a map of emails to a list of account IDs.

    # emails_accounts_map of email to account ID
    {
      "johnsmith@mail.com": [0, 2],
      "john00@mail.com": [0],
      "johnnybravo@mail.com": [1],
      "john_newyork@mail.com": [2],
      "mary@mail.com": [3]
    }
    

  • 1
    L

    Nice hack of converting set into a sorted list


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.