Leetcode: Accounts Merge

 

This question is asked at Facebook, Google, and Microsoft. It is a Union Find problem. Given a list of accounts, where each element accounts[i] is a list of strings, where the first elements accounts[i][0] is the name and the rest of the elements are emails representing emails of the account. We want to merge accounts, especially if there is a common email to both of these accounts. We use union find here, since we are joining certain areas of the email. 

A disjoint data structure is a structure that keeps track of a set of elements partitioned into a number of disjoint operations on such a data structure, and we will discuss the application of the disjoint data structure this way. We want to see if a graph has a cycle or not. Let's consider the following graph: 

For each edge, we make subsets using both vertices of the edge and a cycle is found if the vertices are in the same subset.  We first see vertices 0 and 1. To take union, make node 0 the parent of node 1, or vice versa. 

Now, we process all the edges one by one and see which subsets vertices 0 and 1 are. 

If node 1 is the parent of node 0, then node 0 would be set to 1 in this fashion. If 1 is in subset 1 and 2 is in subset 2, we take union.

The key task here is to connect these emails, which is the perfect case for a union find. To group these emails, each group needs to have a representative, or parent. At the beginning, we will set each email to its own representative and emails in each account should be assigned to the same parent. 

Here's an example:

a b c    //b, c have parent a.

d e f    //e, f have parent d.

g a d  //abc and def are now merged to g.

a-a

b-a 

c-a 

d-d 

e-d 

f-d 

g-g 

a-g 

d-g

here's the union find code. We want to connect the emails here. So, we find the parents, we create new treesets for the parents, then we find the array. 

class Solution {

    public List<List<String>> accountsMerge(List<List<String>> acts) {

        Map<String, String> owner = new HashMap<>();

        Map<String, String> parents = new HashMap<>(); 

        Map<String, TreeSet<String>> unions = new HashMap<>(); 

        //put the parent in itself and the owner as the first element to check if there's a cycle. Also, assign the email to the right order. 

        for(List<String> a : acts) {

            for(int i = 1; i < a.size(); i++) {

                parents.put(a.get(i), a.get(i));

                owner.put(a.get(i), a.get(0)); 

            }

        }

        //find the parent

        for(List<String> a : acts) {

            String p = find(a.get(1), parents); 

            for(int i = 2; i < a.size(); i++) {

                //put the parent node inside. 

                parents.put(find(a.get(i), parents), p); 

            }

        }

        for(List<String> a : acts) {

            String p = find(a.get(1), parents); 

            //put the parent in if we do not contain the new parent. 

            if(!unions.containsKey(p)) {unions.put(p, new TreeSet<>());}

            for(int i = 1; i < a.size(); i++) {

                unions.get(p).add(a.get(i)); 

            }

        }

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

        for(String p: unions.keySet()) {

            //access the treeset.

            //have the treeset for the parent

            List<String> emails = new ArrayList(unions.get(p)); 

            //add the parent to the emails.

            emails.add(0, owner.get(p)); 

                ///add the emails

            res.add(emails);

        }

        //return the list.

        return res;

    }

    

    private String find(String s, Map<String, String> p) {

        if(p.get(s) == s) {

            //return the parent if it is itself

            return s;

        } else {

            //else, traverse back until we find the parent node. 

            return find(p.get(s), p); 

        }

    }

}