Problem

Table: Friends

+-------------+------+
| Column Name | Type |
+-------------+------+
| user_id1    | int  |
| user_id2    | int  |
+-------------+------+
(user_id1, user_id2) is the primary key (combination of columns with unique values) for this table.
Each row contains user id1, user id2, both of whom are friends with each other.

Write a solution to find all pairs of users who are friends with each other and have no mutual friends.

Return the result table ordered byuser_id1, user_id2 inascending **** 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

Input: 
Friends table:
+----------+----------+
| user_id1 | user_id2 | 
+----------+----------+
| 1        | 2        | 
| 2        | 3        | 
| 2        | 4        | 
| 1        | 5        | 
| 6        | 7        | 
| 3        | 4        | 
| 2        | 5        | 
| 8        | 9        | 
+----------+----------+
Output: 
+----------+----------+
| user_id1 | user_id2 | 
+----------+----------+
| 6        | 7        | 
| 8        | 9        | 
+----------+----------+
Explanation: 
- Users 1 and 2 are friends with each other, but they share a mutual friend with user ID 5, so this pair is not included.
- Users 2 and 3 are friends, they both share a mutual friend with user ID 4, resulting in exclusion, similarly for users 2 and 4 who share a mutual friend with user ID 3, hence not included.
- Users 1 and 5 are friends with each other, but they share a mutual friend with user ID 2, so this pair is not included.
- Users 6 and 7, as well as users 8 and 9, are friends with each other, and they don't have any mutual friends, hence included.
- Users 3 and 4 are friends with each other, but their mutual connection with user ID 2 means they are not included, similarly for users 2 and 5 are friends but are excluded due to their mutual connection with user ID 1.
Output table is ordered by user_id1 in ascending order.

Solution

Method 1 – Self Join and Anti Join

Intuition

Two users are friends with no mutual friends if there is no third user who is friends with both. We can use a self join to find all possible mutual friends and then exclude pairs that have any mutual friend.

Approach

  1. For each friendship (user_id1, user_id2), ensure user_id1 < user_id2 to avoid duplicates.
  2. Use a self join to find all possible mutual friends for each pair.
  3. Exclude pairs that have any mutual friend (anti join).
  4. Return all pairs with no mutual friends, ordered by user_id1 and user_id2 ascending.

Code

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

SELECT f1.user_id1, f1.user_id2
FROM Friends f1
WHERE f1.user_id1 < f1.user_id2
  AND NOT EXISTS (
    SELECT 1 FROM Friends f2
    JOIN Friends f3 ON f2.user_id2 = f3.user_id2
    WHERE f2.user_id1 = f1.user_id1
      AND f3.user_id1 = f1.user_id2
      AND f2.user_id2 = f3.user_id2
      AND f2.user_id2 NOT IN (f1.user_id1, f1.user_id2)
  )
ORDER BY f1.user_id1, f1.user_id2;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

SELECT f1.user_id1, f1.user_id2
FROM Friends f1
WHERE f1.user_id1 < f1.user_id2
  AND NOT EXISTS (
    SELECT 1 FROM Friends f2
    JOIN Friends f3 ON f2.user_id2 = f3.user_id2
    WHERE f2.user_id1 = f1.user_id1
      AND f3.user_id1 = f1.user_id2
      AND f2.user_id2 = f3.user_id2
      AND f2.user_id2 NOT IN (f1.user_id1, f1.user_id2)
  )
ORDER BY f1.user_id1, f1.user_id2;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def friends_with_no_mutual(self, df: 'pd.DataFrame') -> 'pd.DataFrame':
        import pandas as pd
        # Ensure user_id1 < user_id2 for unique pairs
        df = df.copy()
        df['min_id'] = df[['user_id1', 'user_id2']].min(axis=1)
        df['max_id'] = df[['user_id1', 'user_id2']].max(axis=1)
        pairs = df[['min_id', 'max_id']].drop_duplicates()
        # Build friend sets
        friends = {}
        for _, row in df.iterrows():
            friends.setdefault(row['user_id1'], set()).add(row['user_id2'])
            friends.setdefault(row['user_id2'], set()).add(row['user_id1'])
        res = []
        for _, row in pairs.iterrows():
            a, b = row['min_id'], row['max_id']
            if friends[a].isdisjoint(friends[b]) or friends[a] == {b}:
                res.append({'user_id1': a, 'user_id2': b})
        return pd.DataFrame(res).sort_values(['user_id1', 'user_id2']).reset_index(drop=True)

Complexity

  • ⏰ Time complexity: O(n^2), where n is the number of users, due to pairwise checks for mutual friends.
  • 🧺 Space complexity: O(n^2), for storing friend sets and pairs.