Accounts Merge medium

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 are emails representing emails of the account. Now, we need to merge all accounts with the same emails. Note that one email can be in multiple accounts. After merging, each email can only appear in one account. Return the accounts in the format as input.

Example 1

Input: accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"]] Output: [["John", "johnsmith@mail.com", "john00@mail.com", "john_newyork@mail.com"], ["John", "johnnybravo@mail.com"]] Explanation: The first and third accounts both have "johnsmith@mail.com", so we merge them.

Example 2

Input: accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin3","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Edward","Edward4@m.co","Edward0@m.co"],["Gabe","Gabe0@m.co","Gabe4@m.co","Gabe2@m.co"]] Output: [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co","Gabe4@m.co","Gabe2@m.co"],["Kevin3","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Edward","Edward4@m.co","Edward0@m.co"]]

Steps

1. Create a graph: Use a graph (adjacency list) to represent the relationships between emails. Each email will be a node. If two emails belong to the same account, add an undirected edge between them.

2. Find connected components: Perform Depth-First Search (DFS) or Breadth-First Search (BFS) to find the connected components in the graph. Each connected component represents a merged account.

3. Merge accounts: For each connected component, gather all the emails and create a merged account list.

Explanation

The core idea is to treat emails as nodes in a graph. If two emails are in the same account, they are connected. Finding connected components identifies all emails belonging to the same merged account.

The DFS function recursively explores the graph, marking visited nodes and collecting all emails within a connected component.

Code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, int> emailToId; // Map email to its ID in the graph
    unordered_map<int, string> idToName; // Map ID to account name
    int idCounter = 0;
    vector<vector<int>> graph; // Adjacency list representing the graph

    // Build the graph
    for (const auto& account : accounts) {
        string name = account[0];
        for (size_t i = 1; i < account.size(); ++i) {
            string email = account[i];
            if (emailToId.find(email) == emailToId.end()) {
                emailToId[email] = idCounter++;
                idToName[idCounter -1] = name;
                graph.push_back({});
            }
        }
        for (size_t i = 1; i < account.size(); ++i) {
            for (size_t j = i + 1; j < account.size(); ++j) {
                int id1 = emailToId[account[i]];
                int id2 = emailToId[account[j]];
                graph[id1].push_back(id2);
                graph[id2].push_back(id1);
            }
        }
    }


    unordered_set<int> visited;
    vector<vector<string>> result;

    // DFS to find connected components
    function<void(int, vector<string>&)> dfs = [&](int u, vector<string>& component) {
        visited.insert(u);
        component.push_back(to_string(u));
        for (int v : graph[u]) {
            if (visited.find(v) == visited.end()) {
                dfs(v, component);
            }
        }
    };

    // Process each connected component
    for (int i = 0; i < idCounter; ++i) {
        if (visited.find(i) == visited.end()) {
            vector<string> component;
            dfs(i, component);
            vector<string> mergedAccount;
            mergedAccount.push_back(idToName[stoi(component[0])]);
            unordered_map<string,int> seen;
            for(auto emailID : component){
                string email = "";
                for(auto const& [key, val] : emailToId){
                    if(val == stoi(emailID)){
                        email = key;
                        break;
                    }
                }
                if(seen.find(email) == seen.end()){
                    mergedAccount.push_back(email);
                    seen[email]++;
                }
            }
            result.push_back(mergedAccount);
        }
    }

    return result;
}

Complexity

• Time Complexity: O(E + V), where E is the number of edges (relationships between emails) and V is the number of vertices (emails). This is dominated by the DFS traversal.
• Space Complexity: O(E + V) to store the graph and other data structures. The space is mainly used for the graph, the emailToId and idToName maps, and the visited set.