LeetCode 1919: Leetcodify Similar Friends Solution

Master LeetCode problem 1919 (Leetcodify Similar Friends), a hard 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.

1919. Leetcodify Similar Friends

Hard

Database

Problem Explanation

Explanation:

Given a list of friends and their similarity relationships, we need to find the groups of similar friends. Two friends are considered similar if they have at least one mutual friend.

To solve this problem, we can use Union-Find data structure. We will iterate through all the similarity relationships and union the friends that are similar. After processing all the relationships, we will have disjoint sets representing the groups of similar friends.

Algorithm:

Initialize a map to store the parent of each friend and a map to store the size of each group.
Initialize the parent of each friend to be itself and the size of each group to be 1.
Iterate through the similarity relationships:
- Find the root parent of both friends in the relationship.
- If the root parents are not the same, union the groups by setting one as the parent of the other and updating the size of the group.
Iterate through all friends and find the root parent of each friend.
Build the groups of similar friends using the root parent of each friend.

Time Complexity:

The time complexity of this algorithm is O(n * α(n)), where n is the number of friends and α(n) is the inverse Ackermann function (almost a constant).

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of friends.

Solution Code

class Solution {
    public List<List<String>> leetcodifySimilarFriends(List<List<String>> friends, List<List<String>> similarities) {
        Map<String, String> parent = new HashMap<>();
        Map<String, Integer> size = new HashMap<>();
        
        for (List<String> friend : friends) {
            String name = friend.get(0);
            parent.put(name, name);
            size.put(name, 1);
        }
        
        for (List<String> similarity : similarities) {
            String friend1 = similarity.get(0);
            String friend2 = similarity.get(1);
            union(parent, size, friend1, friend2);
        }
        
        Map<String, List<String>> groups = new HashMap<>();
        for (String friend : parent.keySet()) {
            String root = find(parent, friend);
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(friend);
        }
        
        return new ArrayList<>(groups.values());
    }
    
    private String find(Map<String, String> parent, String friend) {
        if (!parent.get(friend).equals(friend)) {
            parent.put(friend, find(parent, parent.get(friend)));
        }
        return parent.get(friend);
    }
    
    private void union(Map<String, String> parent, Map<String, Integer> size, String friend1, String friend2) {
        String root1 = find(parent, friend1);
        String root2 = find(parent, friend2);
        if (!root1.equals(root2)) {
            if (size.get(root1) < size.get(root2)) {
                parent.put(root1, root2);
                size.put(root2, size.get(root1) + size.get(root2));
            } else {
                parent.put(root2, root1);
                size.put(root1, size.get(root1) + size.get(root2));
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1919 (Leetcodify Similar Friends)?

This page provides optimized solutions for LeetCode problem 1919 (Leetcodify Similar Friends) 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 1919 (Leetcodify Similar Friends)?

The time complexity for LeetCode 1919 (Leetcodify Similar Friends) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1919 on DevExCode?

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

Back to LeetCode Solutions