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 by user_id1, user_id2 in ascending order.
The result format is in the following example.
Example 1:
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.
Problem Overview: You are given a friendship table representing connections in a social network. The task is to return pairs of users who are friends but do not share any mutual friends. A mutual friend exists if both users are connected to the same third user.
Approach 1: Self Join + Mutual Friend Check (O(n^2) time, O(1) extra space)
Model the friendship network as pairs (user1, user2). For each pair, search for a third user who is connected to both people. This is done with a self join on the friendship table where one join finds friends of the first user and another join finds friends of the second user. If the intersection is empty, the pair has no mutual friends. The query typically uses NOT EXISTS to ensure that no shared neighbor appears in the joined result set.
This approach works well because relational databases are optimized for join operations. The database engine performs index lookups and join filtering internally. You iterate conceptually over each friendship pair and eliminate those with at least one shared connection.
Approach 2: Subquery with Mutual Friend Detection (O(n^2) time, O(1) extra space)
Another way is to check mutual connections using a correlated subquery. For each friendship pair, run a subquery that searches for any user connected to both people. If the subquery returns no rows, the pair qualifies. The structure usually looks like NOT EXISTS (SELECT ...) where the inner query joins the friendship table twice to detect a shared neighbor.
The key insight is that detecting mutual friends is equivalent to checking if the intersection of the two users' friend lists is empty. SQL handles this efficiently using join predicates and filtering. This technique is common in SQL interview problems involving graph-like relationships stored in relational tables.
These strategies rely heavily on relational joins and filtering logic, core ideas in database query design. Understanding how subqueries interact with outer queries is crucial for writing correct and efficient solutions.
Recommended for interviews: The NOT EXISTS subquery solution is the cleanest and most commonly expected answer. It clearly expresses the requirement: return friendship pairs where no mutual friend exists. Showing the self-join logic demonstrates that you understand how relational tables model graph problems, while the subquery version demonstrates practical SQL problem‑solving skill.
First, we list all the friend relationships and record them in table T. Then we find the pairs of friends who do not have common friends.
Next, we can use a subquery to find pairs of friends who do not have common friends, i.e., this pair of friends does not belong to any other person's friends.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self Join to Detect Mutual Friends | O(n^2) | O(1) | When reasoning directly about intersections of friend lists using joins |
| Subquery with NOT EXISTS | O(n^2) | O(1) | Preferred SQL pattern for filtering rows when a related condition must not exist |
| Join + Aggregation Check | O(n^2) | O(n) | Useful when grouping and counting shared neighbors instead of using NOT EXISTS |
Leetcode MEDIUM 3058 - Friends With No Mutual Friends - SELF JOINS in SQL | Everyday Data Science • Everyday Data Science • 725 views views
Practice Friends With No Mutual Friends with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor