What is the time complexity of Accounts Merge?

The optimal solution has a time complexity of O(n*m*log(n*m)).

What is the space complexity of Accounts Merge?

The space complexity is O(n*m).

What data structures are used to solve Accounts Merge?

This problem uses Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union Find, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Accounts Merge?

Insight 1: Union-Find data structure is well-suited for efficiently determining connected components (groups of accounts that need to be merged) based on shared email addresses. Insight 2: Representing emails as nodes in a graph and connecting them if they appear in the same account allows us to identify connected components. Union-Find simplifies this.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Accounts Merge - LeetCode 721 Solution

Q: Which companies ask LeetCode 721. Accounts Merge in interviews?

This problem is frequently asked at Palantir Technologies, PhonePe, Pinterest, Rippling, Roblox and 1 more companies.

Accounts Merge - Complete Solution Guide

Accounts Merge is LeetCode problem 721, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of

Detailed Explanation

The problem asks us to merge accounts based on shared email addresses. We are given a list of accounts, where each account contains a name followed by a list of email addresses. If two accounts share any email address, they belong to the same person and should be merged. The final output should be a list of merged accounts, where each merged account contains the name of the person and a sorted list of unique email addresses associated with that person. Accounts with the same name but no shared emails should be treated as distinct.

Solution Approach

The provided solutions employ the Union-Find algorithm to merge accounts based on shared email addresses. A dictionary (or hash map) is also used to store the name associated with each email. The algorithm iterates through the accounts, connecting emails within the same account using the Union-Find 'union' operation. After processing all accounts, it iterates through the emails again, finding the 'root' (representative) of each email's connected component using the Union-Find 'find' operation. It then groups emails by their root, sorts the emails in each group, and constructs the final merged accounts with the corresponding name.

Step-by-Step Algorithm

Step 1: Initialize a Union-Find data structure to represent the connected components of email addresses. This typically involves creating a 'parent' dictionary where each email initially points to itself.
Step 2: Create a dictionary to store the name associated with each email address. This will be used later to retrieve the correct name for the merged accounts.
Step 3: Iterate through the list of accounts. For each account, associate each email address with the account's name and perform the 'union' operation between the first email in the account and all other emails in the same account. This connects all emails within that account into the same connected component.
Step 4: After processing all accounts, iterate through all email addresses. For each email, find its root (representative) using the 'find' operation. Use another dictionary to group emails by their root.
Step 5: Create the final result. For each group of emails (identified by their root), retrieve the name associated with the group's first email address. Sort the emails in the group and construct a new account containing the name followed by the sorted list of emails.
Step 6: Return the list of merged accounts.

Key Insights

Insight 1: Union-Find data structure is well-suited for efficiently determining connected components (groups of accounts that need to be merged) based on shared email addresses.
Insight 2: Representing emails as nodes in a graph and connecting them if they appear in the same account allows us to identify connected components. Union-Find simplifies this.
Insight 3: Using a hash map (or dictionary) to map emails to names is crucial for associating the correct name with each merged account.

Complexity Analysis

Time Complexity: O(n*m*log(n*m))

Space Complexity: O(n*m)

Topics

This problem involves: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union Find, Sorting.

Companies

Asked at: Palantir Technologies, PhonePe, Pinterest, Rippling, Roblox, Snap.

Accounts Merge | LeetCode 721

Medium

Array Hash Table String Depth-First Search Breadth-First Search Union Find Sorting

Time: O(n*m*log(n*m))Space: O(n*m)

Solution Code

Available in:

import java.util.*;

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> parent = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();

        function find = (i) -> {
            if (!parent.containsKey(i)) {
                parent.put(i, i);
            }
            if (!parent.get(i).equals(i)) {
                parent.put(i, find.apply(parent.get(i)));
            }
            return parent.get(i);
        };

        BiConsumer<String, String> union = (i, j) -> {
            String rootI = find.apply(i);
            String rootJ = find.apply(j);
            if (!rootI.equals(rootJ)) {
                if (rootI.compareTo(rootJ) < 0) {
                    parent.put(rootJ, rootI);
                } else {
                    parent.put(rootI, rootJ);
                }
            }
        };

        for (List<String> account : accounts) {
            String name = account.get(0);
            String firstEmail = account.get(1);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                emailToName.put(email, name);
                union.accept(firstEmail, email);
            }
        }

        Map<String, List<String>> mergedGroups = new HashMap<>();
        for (String email : emailToName.keySet()) {
            String root = find.apply(email);
            mergedGroups.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
        }

        List<List<String>> result = new ArrayList<>();
        for (List<String> emails : mergedGroups.values()) {
            String name = emailToName.get(emails.get(0));
            Collections.sort(emails);
            List<String> mergedAccount = new ArrayList<>();
            mergedAccount.add(name);
            mergedAccount.addAll(emails);
            result.add(mergedAccount);
        }

        return result;
    }

    interface function {
        String apply(String i);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 721: Accounts Merge - Detailed explanation and solution approaches.

Topics

Array Hash Table String Depth-First Search Breadth-First Search Union Find Sorting

Companies

Palantir TechnologiesPhonePePinterestRipplingRobloxSnap

Stats

Difficulty:Medium

Languages:4

Companies:6

Problem #:721

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize a Union-Find data structure to represent the connected components of email addresses. This typically involves creating a 'parent' dictionary where each email initially points to itself.
2
Step 2: Create a dictionary to store the name associated with each email address. This will be used later to retrieve the correct name for the merged accounts.
3
Step 3: Iterate through the list of accounts. For each account, associate each email address with the account's name and perform the 'union' operation between the first email in the account and all other emails in the same account. This connects all emails within that account into the same connected component.
4
Step 4: After processing all accounts, iterate through all email addresses. For each email, find its root (representative) using the 'find' operation. Use another dictionary to group emails by their root.
5
Step 5: Create the final result. For each group of emails (identified by their root), retrieve the name associated with the group's first email address. Sort the emails in the group and construct a new account containing the name followed by the sorted list of emails.
6
Step 6: Return the list of merged accounts.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n*m*log(n*m))

💾

Space Complexity

O(n*m)

📝

Why?

The time complexity is dominated by the sorting step, which occurs after the Union-Find operations. The space complexity is derived from the storage required for the Union-Find data structure (parent dictionary) and the email-to-name mapping, which can grow linearly with the total number of emails across all accounts.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

An alternative approach is to use DFS to traverse the graph of email addresses. We can build an adjacency list where each email is a node, and edges connect emails that appear in the same account. Then, we can perform a DFS starting from any email to find all connected emails, effectively merging the accounts. A set can be used to store visited emails, avoiding infinite loops.

Time: O(n*m), where n is the number of accounts and m is the average number of emails per account. Building the adjacency list takes O(n*m), and DFS takes O(V+E) time, where V is the number of vertices (emails) and E is the number of edges (connections between emails), both bounded by O(n*m). The sorting of emails within each merged account still contributes O(n*m*log(n*m)) time.Space: O(n*m) for storing the adjacency list and the visited set during DFS.

Trade-offs: DFS might be slightly simpler to implement than Union-Find in some cases, but the asymptotic complexity is often the same, and can have a very similar performance profile.

✨

Key Insights

1Insight 1: Union-Find data structure is well-suited for efficiently determining connected components (groups of accounts that need to be merged) based on shared email addresses.
2Insight 2: Representing emails as nodes in a graph and connecting them if they appear in the same account allows us to identify connected components. Union-Find simplifies this.
3Insight 3: Using a hash map (or dictionary) to map emails to names is crucial for associating the correct name with each merged account.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Accounts with the same name but no shared emails. The solution correctly treats these as separate accounts, because no union operation occurs, so the find operations will return different roots.
Edge case 2: An email appearing in multiple accounts with different names. The email will be associated with the name in the first account encountered, and Union-Find merges all connected accounts based on email connectivity, disregarding names after the first association.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to sort the email addresses within each merged account. The problem explicitly requires the email addresses to be sorted.

✗Common mistake 2: Incorrectly associating names with merged accounts. It's important to ensure that the correct name is associated with each merged account, which typically involves using the name from the first account encountered that contains the email addresses.

✗Common mistake 3: Not handling the case where two accounts have the same name but different sets of email addresses, where the sets of emails do not intersect. They should be treated as distinct accounts and not merged.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Social network account merging. This algorithm can be used to merge user accounts on a social network based on shared email addresses or other identifying information.

🏦Real-world scenario 2: Customer data integration. Companies can use this algorithm to integrate customer data from different sources, such as different databases or marketing platforms, by merging records based on shared email addresses or phone numbers.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 2, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Accounts Merge"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?