Problem Description

The Leetcodify Friends Recommendations problem asks you to implement a friend recommendation system based on mutual friends. Given a list of users and their friendships, for a specific user user_id, you need to recommend new friends. A recommended friend is someone who:

• Is not already a direct friend of user_id
• Is not user_id themselves
• Shares at least one mutual friend with user_id

Constraints:

• Each friendship is bidirectional (if A is a friend of B, then B is a friend of A).
• No duplicate friendships.
• Input is provided as a list of pairs friendships, where each pair [a, b] means user a and user b are friends.
• There is only one valid set of recommendations for each user.

Thought Process

The first step is to understand the requirements for recommending friends. For a given user_id, we need to find users who are not already friends (and not themselves), but who share at least one mutual friend with user_id.

A brute-force approach would be to:

• For each user in the network, check if they are not already a friend and not the user themselves.
• For each such user, count how many mutual friends they share with user_id.
• If the count is at least one, add them to the recommendations.

To optimize, we can:

• Build a mapping of each user to their set of friends for fast lookups.
• For each friend of user_id, look at their friends (i.e., friends-of-friends).
• Count how many times each friend-of-friend appears (excluding direct friends and the user themselves).
• The count gives the number of mutual friends.

Solution Approach

Here is a step-by-step breakdown of the algorithm:

1. Build the Friendship Graph:
   • Create a dictionary (hash map) where the key is a user ID and the value is a set of their friends.
   • Iterate through each pair in friendships and add both directions (since friendship is bidirectional).
2. Identify Direct Friends:
   • Get the set of direct friends for user_id.
3. Find Friends-of-Friends:
   • For each direct friend, iterate through their friends.
   • For each friend-of-friend, if they are not user_id and not already a direct friend, increment their mutual friend count in a new hash map.
4. Sort Recommendations:
   • For each candidate, we now have the number of mutual friends.
   • Create a list of candidates who have at least one mutual friend.
   • Sort the list by descending number of mutual friends, then by ascending user ID.
5. Return the Recommendations:
   • Return the sorted list of user IDs as the recommendations.

We use sets for fast membership checks and hash maps for counting, making the approach efficient and clean.

Example Walkthrough

Sample Input:

• friendships = [[1,2], [1,3], [2,4], [3,4], [3,5], [5,6]]
• user_id = 1

Step-by-Step:

1. Build friendship graph:
   • 1: {2,3}
   • 2: {1,4}
   • 3: {1,4,5}
   • 4: {2,3}
   • 5: {3,6}
   • 6: {5}
2. Direct friends of 1: {2, 3}
3. Friends-of-friends:
   • Friends of 2: {1,4} → 4 is not 1 and not a direct friend, so add 4 (mutual count: 1)
   • Friends of 3: {1,4,5} → 4 is not 1 or direct friend, increment 4 (mutual count: 2); 5 is not 1 or direct friend, add 5 (mutual count: 1)
4. Mutual friend counts:
   • 4: 2 mutual friends
   • 5: 1 mutual friend
5. Sort recommendations:
   • 4 (2 mutual friends)
   • 5 (1 mutual friend)

Time and Space Complexity

Brute-force Approach:

• For each user, check against every other user and count mutual friends. This is O(N^2 * F), where N is the number of users and F is the average number of friends.

• Building the friendship graph: O(E), where E is the number of friendship pairs.
• Iterating over friends and their friends: O(F^2), where F is the number of friends of user_id, assuming their friends also have about F friends.
• Sorting recommendations: O(K log K), where K is the number of candidates.
• Overall: Much faster for sparse graphs, typically O(E + F^2 + K log K).

• O(N + E) for the friendship graph and mutual friend counts.

Summary

The Leetcodify Friends Recommendations problem is a classic example of using set operations and hash maps to efficiently find mutual connections in a social network. By building a friendship graph and focusing only on friends-of-friends, we avoid unnecessary computations and achieve an elegant, scalable solution. Sorting by mutual friend count ensures the most relevant suggestions are shown first, making the recommendation system both effective and efficient.

Code Implementation

def recommendFriends(friendships, user_id):
    from collections import defaultdict, Counter

    # Build friendship graph
    graph = defaultdict(set)
    for a, b in friendships:
        graph[a].add(b)
        graph[b].add(a)

    direct_friends = graph[user_id]
    mutual_counts = Counter()

    for friend in direct_friends:
        for fof in graph[friend]:
            if fof != user_id and fof not in direct_friends:
                mutual_counts[fof] += 1

    # Filter candidates with at least 1 mutual friend
    candidates = [(cnt, uid) for uid, cnt in mutual_counts.items()]
    # Sort by descending mutual friend count, then ascending user id
    candidates.sort(key=lambda x: (-x[0], x[1]))
    return [uid for cnt, uid in candidates]
      

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>

using namespace std;

vector<int> recommendFriends(vector<vector<int>>& friendships, int user_id) {
    unordered_map<int, unordered_set<int>> graph;
    for (const auto& p : friendships) {
        graph[p[0]].insert(p[1]);
        graph[p[1]].insert(p[0]);
    }
    const auto& direct = graph[user_id];
    unordered_map<int, int> mutual;
    for (int f : direct) {
        for (int fof : graph[f]) {
            if (fof != user_id && direct.find(fof) == direct.end()) {
                mutual[fof]++;
            }
        }
    }
    vector<pair<int,int>> candidates;
    for (const auto& kv : mutual)
        candidates.push_back({kv.second, kv.first});
    sort(candidates.begin(), candidates.end(), [](const pair<int,int>& a, const pair<int,int>& b){
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });
    vector<int> res;
    for (const auto& p : candidates) res.push_back(p.second);
    return res;
}
      

import java.util.*;

public class Solution {
    public List<Integer> recommendFriends(int[][] friendships, int user_id) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int[] pair : friendships) {
            graph.computeIfAbsent(pair[0], k -> new HashSet<>()).add(pair[1]);
            graph.computeIfAbsent(pair[1], k -> new HashSet<>()).add(pair[0]);
        }
        Set<Integer> direct = graph.getOrDefault(user_id, new HashSet<>());
        Map<Integer, Integer> mutual = new HashMap<>();
        for (int f : direct) {
            for (int fof : graph.getOrDefault(f, new HashSet<>())) {
                if (fof != user_id && !direct.contains(fof)) {
                    mutual.put(fof, mutual.getOrDefault(fof, 0) + 1);
                }
            }
        }
        List<int[]> candidates = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : mutual.entrySet()) {
            candidates.add(new int[]{e.getValue(), e.getKey()});
        }
        candidates.sort((a, b) -> b[0] != a[0] ? b[0] - a[0] : a[1] - b[1]);
        List<Integer> res = new ArrayList<>();
        for (int[] pair : candidates) res.add(pair[1]);
        return res;
    }
}
      

function recommendFriends(friendships, user_id) {
    const graph = {};
    for (const [a, b] of friendships) {
        if (!graph[a]) graph[a] = new Set();
        if (!graph[b]) graph[b] = new Set();
        graph[a].add(b);
        graph[b].add(a);
    }
    const direct = graph[user_id] || new Set();
    const mutual = {};
    for (const friend of direct) {
        for (const fof of graph[friend]) {
            if (fof !== user_id && !direct.has(fof)) {
                mutual[fof] = (mutual[fof] || 0) + 1;
            }
        }
    }
    const candidates = [];
    for (const [uid, cnt] of Object.entries(mutual)) {
        candidates.push([cnt, Number(uid)]);
    }
    candidates.sort((a, b) => b[0] - a[0] || a[1] - b[1]);
    return candidates.map(x => x[1]);
}