Strong Friendship

Problem

Table: Friendship

+-------------+------+
| Column Name | Type |
+-------------+------+
| user1_id    | int  |
| user2_id    | int  |
+-------------+------+
(user1_id, user2_id) is the primary key (combination of columns with unique values) for this table.
Each row of this table indicates that the users user1_id and user2_id are friends.
Note that user1_id < user2_id.

A friendship between a pair of friends x and y is strong if x and y have at least three common friends.

Write a solution to find all the strong friendships.

Note that the result table should not contain duplicates with user1_id < user2_id.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


Input: 
Friendship table:
+----------+----------+
| user1_id | user2_id |
+----------+----------+
| 1        | 2        |
| 1        | 3        |
| 2        | 3        |
| 1        | 4        |
| 2        | 4        |
| 1        | 5        |
| 2        | 5        |
| 1        | 7        |
| 3        | 7        |
| 1        | 6        |
| 3        | 6        |
| 2        | 6        |
+----------+----------+
Output: 
+----------+----------+---------------+
| user1_id | user2_id | common_friend |
+----------+----------+---------------+
| 1        | 2        | 4             |
| 1        | 3        | 3             |
+----------+----------+---------------+
Explanation: 
Users 1 and 2 have 4 common friends (3, 4, 5, and 6).
Users 1 and 3 have 3 common friends (2, 6, and 7).
We did not include the friendship of users 2 and 3 because they only have two common friends (1 and 6).

Solution

Method 1 - SQL Self-Join to Find Common Friends

Intuition

To find strong friendships, we need to count the number of common friends for each pair (x, y). A common friend z is such that both (x, z) and (y, z) exist in the Friendship table. We can use self-joins to find all such (x, y, z) triplets, then group by (x, y) and count the number of z’s.

Approach

For each pair (x, y), find all users z who are friends with both x and y.
Count the number of such z for each (x, y).
Return only those (x, y) pairs with at least 3 common friends.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


SELECT
  f1.user1_id AS user1_id,
  f2.user1_id AS user2_id,
  COUNT(*) AS common_friend
FROM Friendship f1
JOIN Friendship f2
  ON f1.user2_id = f2.user2_id AND f1.user1_id < f2.user1_id
JOIN Friendship f3
  ON f3.user1_id = f1.user2_id AND f3.user2_id = f2.user2_id
GROUP BY f1.user1_id, f2.user1_id
HAVING COUNT(*) >= 3;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import java.util.*;
class Solution {
    public List<int[]> strongFriendship(int[][] friendships) {
        Map<Integer, Set<Integer>> friends = new HashMap<>();
        for (int[] f : friendships) {
            friends.computeIfAbsent(f[0], k -> new HashSet<>()).add(f[1]);
            friends.computeIfAbsent(f[1], k -> new HashSet<>()).add(f[0]);
        }
        List<int[]> res = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        for (int x : friends.keySet()) {
            for (int y : friends.get(x)) {
                if (x < y && seen.add(x + "," + y)) {
                    Set<Integer> common = new HashSet<>(friends.get(x));
                    common.retainAll(friends.get(y));
                    if (common.size() >= 3) {
                        res.add(new int[]{x, y, common.size()});
                    }
                }
            }
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


import pandas as pd
def strong_friendship(friendship: pd.DataFrame) -> pd.DataFrame:
    from collections import defaultdict
    friends = defaultdict(set)
    for _, row in friendship.iterrows():
        friends[row['user1_id']].add(row['user2_id'])
        friends[row['user2_id']].add(row['user1_id'])
    res = []
    for x in friends:
        for y in friends[x]:
            if x < y:
                common = friends[x] & friends[y]
                if len(common) >= 3:
                    res.append({'user1_id': x, 'user2_id': y, 'common_friend': len(common)})
    return pd.DataFrame(res)

Complexity

⏰ Time complexity: O(n^2 * k) where n is the number of users and k is the average number of friends per user (for the brute-force approach).
🧺 Space complexity: O(nk) for storing the friendship graph.

Problem#

Examples#

Solution#

Method 1 - SQL Self-Join to Find Common Friends#

Intuition#

Approach#

Code#

Complexity#