D
DevExCode

LeetCode 721: Accounts Merge Solution

Master LeetCode problem 721 (Accounts Merge), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use a graph-based approach where each email is a node and if two emails are in the same account, we connect them with an edge. This way, accounts that belong to the same person will form a connected component in the graph. We can then traverse these connected components to merge the accounts.

  1. Create a graph where each email is a node and each account is an edge connecting the emails within the same account.
  2. Traverse the graph to find connected components (accounts belonging to the same person).
  3. For each connected component, sort the emails and add them to the result list along with the account name.

Time complexity: O(NlogN) where N is the total number of emails across all accounts (NlogN for sorting emails in each account). Space complexity: O(N) for storing the graph and the result.

:

Solution Code

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap<>();
        Map<String, List<String>> graph = new HashMap<>();
        
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                emailToName.put(account.get(i), name);
                if (!graph.containsKey(account.get(i))) {
                    graph.put(account.get(i), new ArrayList<>());
                }
                if (i == 1) continue;
                graph.get(account.get(i)).add(account.get(i - 1));
                graph.get(account.get(i - 1)).add(account.get(i));
            }
        }
        
        Set<String> visited = new HashSet<>();
        List<List<String>> mergedAccounts = new ArrayList<>();
        
        for (String email : graph.keySet()) {
            if (visited.contains(email)) continue;
            List<String> connectedComponent = new ArrayList<>();
            dfs(graph, email, visited, connectedComponent);
            Collections.sort(connectedComponent);
            connectedComponent.add(0, emailToName.get(email));
            mergedAccounts.add(connectedComponent);
        }
        
        return mergedAccounts;
    }
    
    private void dfs(Map<String, List<String>> graph, String email, Set<String> visited, List<String> connectedComponent) {
        visited.add(email);
        connectedComponent.add(email);
        for (String neighbor : graph.get(email)) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, connectedComponent);
            }
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 721 (Accounts Merge)?

This page provides optimized solutions for LeetCode problem 721 (Accounts Merge) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 721 (Accounts Merge)?

The time complexity for LeetCode 721 (Accounts Merge) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 721 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 721 in Java, C++, or Python.

Back to LeetCode Solutions