Friends With No Mutual Friends - Practice Coding Problems

Friends With No Mutual Friends - Problem

Database Medium

Given a Friends table that represents friendship relationships, find all pairs of users who are friends with each other but have no mutual friends.

The Friends table contains pairs of user IDs where each row indicates that user_id1 and user_id2 are friends with each other. The friendship relationship is bidirectional.

Return the result table ordered by user_id1, user_id2 in ascending order.

Table Schema

Friends

Column Name	Type	Description
`user_id1` PK	int	First user in the friendship pair
`user_id2` PK	int	Second user in the friendship pair

Primary Key: (user_id1, user_id2)

Note: Each row represents a bidirectional friendship between user_id1 and user_id2

Input & Output

Example 1 — Mixed Friendship Network

Input Table:

user_id1	user_id2
1	2
1	3
2	3
4	5

Output:

user_id1	user_id2
4	5

💡 Note:

Users 1, 2, and 3 form a triangle where each pair has a mutual friend: (1,2) share friend 3, (1,3) share friend 2, and (2,3) share friend 1. Only users 4 and 5 are friends with no mutual connections.

Example 2 — All Isolated Pairs

Input Table:

user_id1	user_id2
1	2
3	4
5	6

Output:

user_id1	user_id2
1	2
3	4
5	6

💡 Note:

All friendship pairs are isolated - none of them share mutual friends, so all pairs are returned in the result.

Example 3 — No Valid Pairs

Input Table:

user_id1	user_id2
1	2
1	3
2	3
1	4
2	4
3	4

Output:

user_id1	user_id2

💡 Note:

This forms a complete graph where every pair of users has mutual friends. For example, (1,2) share friends 3 and 4, so no pairs qualify as having no mutual friends.

Constraints

1 ≤ user_id1, user_id2 ≤ 10^6
user_id1 ≠ user_id2
All friendship relationships are bidirectional

Visualization

Tap to expand

Understanding the Visualization

Input

Friendship pairs table

Analysis

Check for mutual friend connections

Filter

Return pairs without mutual friends

Key Takeaway

🎯 Key Insight: Use NOT EXISTS with self-joins to efficiently identify friendship pairs without mutual connections

Asked in

F Facebook 28 L LinkedIn 22 T Twitter 15

Use self-joins with NOT EXISTS to identify friendship pairs that don't share any mutual connections. Create a normalized view of bidirectional friendships, then exclude pairs with mutual friends.

Table Schema

Friends

Column Name	Type	Description
`user_id1` PK	int	First user in the friendship pair
`user_id2` PK	int	Second user in the friendship pair

Primary Key: (user_id1, user_id2)

Note: Each row represents a bidirectional friendship between user_id1 and user_id2

Common Approaches

Approach	Time	Space	Notes
✓ Self-Join with NOT EXISTS	O(n³)	O(n)	Use self-joins to identify mutual friends and exclude those pairs

Self-Join with NOT EXISTS — Algorithm Steps

Step 1: Create a normalized view of all friendships (both directions)
Step 2: Use NOT EXISTS to exclude pairs with mutual friends
Step 3: Order results by user_id1, user_id2

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Friends

List all friendship pairs

Check Mutual

Use self-joins to find mutual friends

Filter

Exclude pairs with mutual friends

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested joins to check for mutual friends

⚠ Quadratic Growth

Space Complexity

O(n)

Temporary storage for friendship combinations

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~18 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Table Schema

Input & Output

Constraints

Visualization

Related Problems

Table Schema

Common Approaches

Self-Join with NOT EXISTS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler