Skip to main content
Talentd

Friends With No Mutual Friends - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase5 min read
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solution

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.

Code

MySQLPython

MySQL

Python

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self Join to Detect Mutual FriendsO(n^2)O(1)When reasoning directly about intersections of friend lists using joins
Subquery with NOT EXISTSO(n^2)O(1)Preferred SQL pattern for filtering rows when a related condition must not exist
Join + Aggregation CheckO(n^2)O(n)Useful when grouping and counting shared neighbors instead of using NOT EXISTS

Video Solution

Leetcode MEDIUM 3058 - Friends With No Mutual Friends - SELF JOINS in SQL | Everyday Data Science • Everyday Data Science • 767 views views

Frequently Asked Questions

Is Friends With No Mutual Friends easy or hard?
The problem is rated Medium because the SQL logic requires understanding self joins, subqueries, and how to detect intersections between two users' friend lists. The challenge is translating a graph concept into correct relational query logic.
Friends With No Mutual Friends Python/Java solution
On database platforms the solution is written in SQL using joins or NOT EXISTS subqueries. If implemented in Python, the problem can be modeled with adjacency sets where each user maps to a set of friends, and mutual friends are checked using set intersection operations.
How to solve Friends With No Mutual Friends in O(n)?
An exact O(n) solution is generally not achievable in standard SQL because detecting mutual friends requires comparing two users' friend lists. The best practical solution uses joins or NOT EXISTS subqueries, which behave closer to O(n^2) in the worst case depending on the number of friendships.
What is the best approach for Friends With No Mutual Friends?
The most practical solution uses a SQL NOT EXISTS subquery. For each friendship pair, the query checks whether a third user is connected to both people. If no such row exists, the pair has no mutual friends. This approach clearly expresses the logic and typically runs in O(n^2) time depending on table size and indexing.
Is Friends With No Mutual Friends asked at Google/Amazon/Meta?
Graph-style SQL problems like this appear in database and data engineer interviews at companies such as Amazon, Meta, and Google. They test the ability to model relationships with joins, detect intersections between sets, and write efficient filtering queries using NOT EXISTS or subqueries.
What data structure is used in Friends With No Mutual Friends?
Conceptually the problem models a graph where users are nodes and friendships are edges. In SQL, this graph is stored in a relational table and processed using joins and subqueries. The logic effectively checks whether the intersection of two adjacency lists is empty.
What is the time complexity of Friends With No Mutual Friends?
The typical SQL solution runs in about O(n^2) time because each friendship pair may be compared with other rows to detect a shared neighbor. Database optimizers and indexes can reduce the practical cost, but logically the query performs pairwise comparisons across the friendship relationships.

Ready to solve this problem?

Practice Friends With No Mutual Friends with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary