Problem Description

The "Friend Requests II: Who Has the Most Friends" problem asks you to determine which user has the most friends in a social network, given a list of friend requests. Each friend request is a pair [user1, user2] indicating that user1 and user2 become friends. Friendship is bidirectional: if A is friends with B, then B is friends with A.

Your task is to count the number of unique friends each user has and return the user(s) with the maximum number of friends. If multiple users tie for the most friends, return all of them.

Key Constraints:

• Friendship pairs may appear multiple times; only count unique friends per user.
• Do not count self-friendship (a user cannot be friends with themselves).
• Return the user(s) with the highest number of friends.

Thought Process

At first glance, one might consider iterating through each possible user and counting their friends by scanning the entire list for each user. However, this brute-force method would be very inefficient for large datasets.

Instead, we can recognize that this is a classic case of counting unique relationships in a network. By using a data structure that efficiently tracks each user's friends, we can avoid repeated scanning and ensure that each friendship is only counted once per user.

The main challenge is to ensure that we don't double-count friendships (since they are bidirectional), and that we efficiently track the count for each user. Using sets for each user allows us to maintain uniqueness automatically.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Use a dictionary (hash map) to map each user to a set of their friends. This ensures that each friend is only counted once per user, and lookups and insertions are fast.
2. Iterate through each friend request:
   • For each pair [user1, user2], add user2 to user1's set and user1 to user2's set.
   • Skip requests where user1 == user2 (no self-friendship).
3. Calculate the number of friends for each user by taking the size of each user's set.
4. Find the maximum friend count.
5. Collect all users who have this maximum friend count.
6. Return the list of users with the most friends.

Using sets ensures that duplicate friendships are not counted, and using a hash map allows us to efficiently look up and update each user's friends.

Example Walkthrough

Let's consider the following sample input:

friend_requests = [[1, 2], [2, 3], [1, 3], [1, 2], [4, 1], [4, 2]]

1. Process [1, 2]: 1's friends = {2}, 2's friends = {1}
2. Process [2, 3]: 2's friends = {1, 3}, 3's friends = {2}
3. Process [1, 3]: 1's friends = {2, 3}, 3's friends = {1, 2}
4. Process [1, 2] again: already friends, sets unchanged.
5. Process [4, 1]: 4's friends = {1}, 1's friends = {2, 3, 4}
6. Process [4, 2]: 4's friends = {1, 2}, 2's friends = {1, 3, 4}

Final friend sets:

• 1: {2, 3, 4} (3 friends)
• 2: {1, 3, 4} (3 friends)
• 3: {1, 2} (2 friends)
• 4: {1, 2} (2 friends)

Time and Space Complexity

• Brute-force approach: For each user, scan the entire list of friend requests, leading to O(N * U) time, where N is the number of friend requests and U is the number of users.
• Optimized approach:
  • Processing each friend request is O(1) using sets and hash maps, so total processing is O(N).
  • Building the result requires a single pass over the users: O(U).
  • Overall time complexity: O(N + U).
  • Space complexity: O(N), since in the worst case each request is unique and all users are friends with each other.

Summary

By using a hash map of sets, we efficiently track each user's unique friends as we process the friend requests. This ensures we avoid duplicate counting and can quickly determine which user(s) have the most friends. The solution is both elegant and efficient, making good use of data structures to solve the problem in linear time.

Code Implementation

def users_with_most_friends(friend_requests):
    from collections import defaultdict

    friends = defaultdict(set)

    for u, v in friend_requests:
        if u == v:
            continue  # Skip self-friendship
        friends[u].add(v)
        friends[v].add(u)

    max_count = 0
    result = []

    for user, fr_set in friends.items():
        cnt = len(fr_set)
        if cnt > max_count:
            max_count = cnt
            result = [user]
        elif cnt == max_count:
            result.append(user)

    return result
      

#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> usersWithMostFriends(const vector<vector<int>>& friendRequests) {
    unordered_map<int, unordered_set<int>> friends;

    for (const auto& req : friendRequests) {
        int u = req[0], v = req[1];
        if (u == v) continue;
        friends[u].insert(v);
        friends[v].insert(u);
    }

    int maxCount = 0;
    vector<int> result;

    for (const auto& kv : friends) {
        int cnt = kv.second.size();
        if (cnt > maxCount) {
            maxCount = cnt;
            result.clear();
            result.push_back(kv.first);
        } else if (cnt == maxCount) {
            result.push_back(kv.first);
        }
    }

    return result;
}
      

import java.util.*;

public class Solution {
    public List<Integer> usersWithMostFriends(int[][] friendRequests) {
        Map<Integer, Set<Integer>> friends = new HashMap<>();

        for (int[] req : friendRequests) {
            int u = req[0], v = req[1];
            if (u == v) continue;
            friends.computeIfAbsent(u, k -> new HashSet<>()).add(v);
            friends.computeIfAbsent(v, k -> new HashSet<>()).add(u);
        }

        int maxCount = 0;
        List<Integer> result = new ArrayList<>();

        for (Map.Entry<Integer, Set<Integer>> entry : friends.entrySet()) {
            int cnt = entry.getValue().size();
            if (cnt > maxCount) {
                maxCount = cnt;
                result.clear();
                result.add(entry.getKey());
            } else if (cnt == maxCount) {
                result.add(entry.getKey());
            }
        }

        return result;
    }
}
      

function usersWithMostFriends(friendRequests) {
    const friends = new Map();

    for (const [u, v] of friendRequests) {
        if (u === v) continue;
        if (!friends.has(u)) friends.set(u, new Set());
        if (!friends.has(v)) friends.set(v, new Set());
        friends.get(u).add(v);
        friends.get(v).add(u);
    }

    let maxCount = 0;
    let result = [];

    for (const [user, frSet] of friends.entries()) {
        const cnt = frSet.size;
        if (cnt > maxCount) {
            maxCount = cnt;
            result = [user];
        } else if (cnt === maxCount) {
            result.push(user);
        }
    }

    return result;
}