Accounts merge

Pre Requisite: Disjoint Set

Intuition:

To identify if two accounts have a common email, iterating over two accounts of the same name and checking each email can be costly.
A more efficient way involves visualizing the set of emails of each account as a graph, forming various connected components. Set of emails belonging to a person form a single node. Each mail can be placed under a set representing that the email belongs to that person. If an email is found to be already associated with some other person, a common email is found, which means all the emails in both the sets belong to a single person and thus, merging of accounts(sets) must be done.

How to handle merging of accounts?

The data structure that is the best fit when it comes to handling merge/union operation is Disjoint Set. Hence, whenever the two sets(accounts) are found to have a common email, the merge operation can be performed in constant time.

Understanding:

To store the mails belonging to a single person, a hashmap can be used which will provide constant look-up time which will be efficient to check if the mails already belonging to a person or not.

Approach:

Initialize a DSU structure to keep track of connected components (emails belonging to the same person).
Traverse through each account and its emails. For each email, if it's seen for the first time, map it to the current account index. If the email has been seen before, union the current account index with the previously mapped account index.
Create a list to collect emails for each connected component.
Traverse the email-to-node mapping to collect all emails under their ultimate parent node.
For each component, sort the emails and prepend the owner's name. Collect all the accounts and sort them by name.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
public:
    /* To store the ranks, parents and 
    sizes of different set of vertices */
    vector<int> rank, parent, size;

    // Constructor
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    // Function to find ultimate parent
    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }
    
    // Function to implement union by rank
    void unionByRank(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }
    
    // Function to implement union by size
    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

// Solution class
class Solution{
public:

    // Function to marge the accounts
    vector<vector<string>> accountsMerge(vector<vector<string>> accounts){

        int n = accounts.size(); // Number of accounts
        
        // Disjoint Set data structure
        DisjointSet ds(n);
        
        // Hashmap to store the pair: {mails, node}
        unordered_map<string, int> mapMailNode;
        
        // Iterate on all the accounts
        for (int i=0; i < n; i++) {
            
            // Iterate on all the mails of the person
            for (int j = 1; j < accounts[i].size(); j++) {
                
                // Get the mail
                string mail = accounts[i][j];
                
                // If this mail was not already existing
                if (mapMailNode.find(mail) == 
                    mapMailNode.end()) {
                    
                    // Add it to the hashmap
                    mapMailNode[mail] = i;
                }
                
                /* Otherwise join it with 
                the previous component */
                else {
                    
                    // Unite the components
                    ds.unionBySize(i, mapMailNode[mail]);
                }
            }
        }
        
        // To store the merged mails
        vector<string> mergedMail[n];
        
        // Iterate on the Hashmap
        for (auto it : mapMailNode) {
            
            string mail = it.first; // Mail
            int node = ds.findUPar(it.second); // Node
            
            // Add the merged mail to the list
            mergedMail[node].push_back(mail);
        }
        
        // To return the result
        vector<vector<string>> ans;
        
        // Iterate on all list of merged mails
        for (int i = 0; i < n; i++) {
            
            /* If a person has no mails, 
            skip the iteration */
            if (mergedMail[i].size() == 0) 
                continue;
                
            // Otherwise, add all the merged mails of person 
            sort(mergedMail[i].begin(), mergedMail[i].end());
            vector<string> temp;
            temp.push_back(accounts[i][0]);
            for (auto it : mergedMail[i]) {
                temp.push_back(it);
            }
            ans.push_back(temp);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};


int main() {
    int n = 4;
    vector<vector<string>> accounts = {
        {"John","johnsmith@mail.com","john_newyork@mail.com"},
        {"John","johnsmith@mail.com","john00@mail.com"},
        {"Mary","mary@mail.com"},
        {"John","johnnybravo@mail.com"}
    };

    // Creating instance of Solution class
    Solution sol;
    
    // Function call to merge the accounts
    vector<vector<string>> ans;
    ans = sol.accountsMerge(accounts);
    
    // Output
    cout << "The mareged accounts are:\n";
    for(int i=0; i < ans.size(); i++) {
        for(int j = 0; j < ans[i].size(); j++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}
import java.util.*;

class DisjointSet {
    /* To store the ranks, parents and 
    sizes of different set of vertices */
    int[] rank, parent, size;

    // Constructor
    DisjointSet(int n) {
        rank = new int[n + 1];
        parent = new int[n + 1];
        size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // Function to find ultimate parent
    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }

    // Function to implement union by rank
    void unionByRank(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }

    // Function to implement union by size
    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
}


// Solution class
class Solution {
    
    // Function to merge the accounts
    static List<List<String>> accountsMerge(List<List<String>> accounts) {

        int n = accounts.size(); // Number of accounts
        
        // Disjoint Set data structure
        DisjointSet ds = new DisjointSet(n);

        // Hashmap to store the pair: {mails, node}
        Map<String, Integer> mapMailNode = new HashMap<>();
        
        // Iterate on all the accounts
        for (int i = 0; i < n; i++) {
            
            // Iterate on all the mails of the person
            for (int j = 1; j < accounts.get(i).size(); j++) {
                
                // Get the mail
                String mail = accounts.get(i).get(j);
                
                // If this mail was not already existing
                if (!mapMailNode.containsKey(mail)) {
                    
                    // Add it to the hashmap
                    mapMailNode.put(mail, i);
                }
                
                /* Otherwise join it with 
                the previous component */
                else {
                    
                    // Unite the components
                    ds.unionBySize(i, mapMailNode.get(mail));
                }
            }
        }
        
        // To store the merged mails
        List<List<String>> mergedMail = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            mergedMail.add(new ArrayList<>());
        }

        // Iterate on the Hashmap
        for (Map.Entry<String, Integer> entry : mapMailNode.entrySet()) {
            
            String mail = entry.getKey(); // Mail
            int node = ds.findUPar(entry.getValue()); // Node
            
            // Add the merged mail to the list
            mergedMail.get(node).add(mail);
        }
        
        // To return the result
        List<List<String>> ans = new ArrayList<>();
        
        // Iterate on all list of merged mails
        for (int i = 0; i < n; i++) {
            
            /* If a person has no mails, 
            skip the iteration */
            if (mergedMail.get(i).isEmpty()) 
                continue;
                
            // Otherwise, add all the merged mails of person 
            Collections.sort(mergedMail.get(i));
            List<String> temp = new ArrayList<>();
            temp.add(accounts.get(i).get(0));
            temp.addAll(mergedMail.get(i));
            ans.add(temp);
        }
        ans.sort(Comparator.comparing(list -> list.get(0)));
        return ans;
    }
    
    public static void main(String[] args) {
        int n = 4;
        List<List<String>> accounts = Arrays.asList(
            Arrays.asList("John","johnsmith@mail.com","john_newyork@mail.com"),
            Arrays.asList("John","johnsmith@mail.com","john00@mail.com"),
            Arrays.asList("Mary","mary@mail.com"),
            Arrays.asList("John","johnnybravo@mail.com")
        );

        // Function call to merge the accounts
        List<List<String>> ans = accountsMerge(accounts);
        
        // Output
        System.out.println("The merged accounts are:");
        for (List<String> account : ans) {
            System.out.println(String.join(" ", account));
        }
    }
}
class DisjointSet:
    # To store the ranks, parents and 
    # sizes of different set of vertices
    def __init__(self, n):
        self.rank = [0] * (n + 1)
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)
    
    # Function to find ultimate parent
    def findUPar(self, node):
        if node == self.parent[node]:
            return node
        self.parent[node] = self.findUPar(self.parent[node])
        return self.parent[node]
    
    # Function to implement union by rank
    def unionByRank(self, u, v):
        ulp_u = self.findUPar(u)
        ulp_v = self.findUPar(v)
        if ulp_u == ulp_v: return
        if self.rank[ulp_u] < self.rank[ulp_v]:
            self.parent[ulp_u] = ulp_v
        elif self.rank[ulp_v] < self.rank[ulp_u]:
            self.parent[ulp_v] = ulp_u
        else:
            self.parent[ulp_v] = ulp_u
            self.rank[ulp_u] += 1
    
    # Function to implement union by size
    def unionBySize(self, u, v):
        ulp_u = self.findUPar(u)
        ulp_v = self.findUPar(v)
        if ulp_u == ulp_v: return
        if self.size[ulp_u] < self.size[ulp_v]:
            self.parent[ulp_u] = ulp_v
            self.size[ulp_v] += self.size[ulp_u]
        else:
            self.parent[ulp_v] = ulp_u
            self.size[ulp_u] += self.size[ulp_v]

# Solution class
class Solution:
    
    # Function to merge the accounts
    def accountsMerge(self, accounts):
        n = len(accounts) # Number of accounts
        
        # Disjoint Set data structure
        ds = DisjointSet(n)
        
        # Hashmap to store the pair: {mails, node}
        mapMailNode = {}
        
        # Iterate on all the accounts
        for i in range(n):
            
            # Iterate on all the mails of the person
            for j in range(1, len(accounts[i])):
                
                # Get the mail
                mail = accounts[i][j]
                
                # If this mail was not already existing
                if mail not in mapMailNode:
                    
                    # Add it to the hashmap
                    mapMailNode[mail] = i
                
                # Otherwise join it with the previous component
                else:
                    # Unite the components
                    ds.unionBySize(i, mapMailNode[mail])
        
        # To store the merged mails
        mergedMail = [[] for _ in range(n)]
        
        # Iterate on the Hashmap
        for mail, node in mapMailNode.items():
            root = ds.findUPar(node)
            mergedMail[root].append(mail)
        
        # To return the result
        ans = []
        
        # Iterate on all list of merged mails
        for i in range(n):
            
            # If a person has no mails, skip the iteration
            if not mergedMail[i]:
                continue
            
            # Otherwise, add all the merged mails of person
            mergedMail[i].sort()
            temp = [accounts[i][0]] + mergedMail[i]
            ans.append(temp)
        
        ans.sort()
        return ans

if __name__ == "__main__":
    n = 4
    accounts = [
        ["John","johnsmith@mail.com","john_newyork@mail.com"],
        ["John","johnsmith@mail.com","john00@mail.com"],
        ["Mary","mary@mail.com"],
        ["John","johnnybravo@mail.com"]
    ]

    # Creating instance of Solution class
    sol = Solution()
    
    # Function call to merge the accounts
    ans = sol.accountsMerge(accounts)
    
    # Output
    print("The merged accounts are:")
    for account in ans:
        print(" ".join(account))
class DisjointSet {
    /* To store the ranks, parents and 
    sizes of different set of vertices */
    constructor(n) {
        this.rank = new Array(n + 1).fill(0);
        this.parent = new Array(n + 1).fill(0).map((_, i) => i);
        this.size = new Array(n + 1).fill(1);
    }

    // Function to find ultimate parent
    findUPar(node) {
        if (node === this.parent[node])
            return node;
        this.parent[node] = this.findUPar(this.parent[node]);
        return this.parent[node];
    }

    // Function to implement union by rank
    unionByRank(u, v) {
        let ulp_u = this.findUPar(u);
        let ulp_v = this.findUPar(v);
        if (ulp_u === ulp_v) return;
        if (this.rank[ulp_u] < this.rank[ulp_v]) {
            this.parent[ulp_u] = ulp_v;
        } else if (this.rank[ulp_v] < this.rank[ulp_u]) {
            this.parent[ulp_v] = ulp_u;
        } else {
            this.parent[ulp_v] = ulp_u;
            this.rank[ulp_u]++;
        }
    }

    // Function to implement union by size
    unionBySize(u, v) {
        let ulp_u = this.findUPar(u);
        let ulp_v = this.findUPar(v);
        if (ulp_u === ulp_v) return;
        if (this.size[ulp_u] < this.size[ulp_v]) {
            this.parent[ulp_u] = ulp_v;
            this.size[ulp_v] += this.size[ulp_u];
        } else {
            this.parent[ulp_v] = ulp_u;
            this.size[ulp_u] += this.size[ulp_v];
        }
    }
}

// Solution class
class Solution {
    
    // Function to merge the accounts
    accountsMerge(accounts) {
        let n = accounts.length; // Number of accounts
        
        // Disjoint Set data structure
        let ds = new DisjointSet(n);
        
        // Hashmap to store the pair: {mails, node}
        let mapMailNode = new Map();
        
        // Iterate on all the accounts
        for (let i = 0; i < n; i++) {
            
            // Iterate on all the mails of the person
            for (let j = 1; j < accounts[i].length; j++) {
                
                // Get the mail
                let mail = accounts[i][j];
                
                // If this mail was not already existing
                if (!mapMailNode.has(mail)) {
                    
                    // Add it to the hashmap
                    mapMailNode.set(mail, i);
                }
                
                /* Otherwise join it with 
                the previous component */
                else {
                    
                    // Unite the components
                    ds.unionBySize(i, mapMailNode.get(mail));
                }
            }
        }
        
        // To store the merged mails
        let mergedMail = Array.from({ length: n }, () => []);
        
        // Iterate on the Hashmap
        for (let [mail, node] of mapMailNode.entries()) {
            let root = ds.findUPar(node);
            mergedMail[root].push(mail);
        }
        
        // To return the result
        let ans = [];
        
        // Iterate on all list of merged mails
        for (let i = 0; i < n; i++) {
            
            /* If a person has no mails, 
            skip the iteration */
            if (mergedMail[i].length === 0) 
                continue;
                
            // Otherwise, add all the merged mails of person 
            mergedMail[i].sort();
            let temp = [accounts[i][0], ...mergedMail[i]];
            ans.push(temp);
        }
        ans.sort((a, b) => a[0].localeCompare(b[0]));
        return ans;
    }
}

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

// Creating instance of Solution class
let sol = new Solution();

// Function call to merge the accounts
let ans = sol.accountsMerge(accounts);

// Output
console.log("The merged accounts are:");
for (let account of ans) {
    console.log(account.join(" "));
}

Complexity Analysis:

Time Complexity: O(N+E) + O(E*4ɑ) + O(N*(ElogE + E)) (where E = no. of emails)

Visiting all the emails takes O(N+E) time.
In the worst case, all the accounts can be merged taking O(E*4ɑ) time.
All the emails to the result list and Sorting the emails take O(N*(ElogE + E)) times.

Space Complexity: O(N+E)

The hashmap will store all the emails taking O(E) space.
The disjoint set data structure uses parent and size/rank arrays taking O(N) space.
The resulting list will take up O(E) space.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

How to handle merging of accounts?

Understanding:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code