Strong Friendship - Problem

Table: Friendship

Column NameType
user1_idint
user2_idint

(user1_id, user2_id) is the primary key for this table.

Each row indicates that 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: The result table should not contain duplicates with user1_id < user2_id.

Return the result table in any order.

Table Schema

Friendship
Column Name Type Description
user1_id PK int First user in friendship (smaller ID)
user2_id PK int Second user in friendship (larger ID)
Primary Key: (user1_id, user2_id)
Note: Each row represents a friendship where user1_id < user2_id

Input & Output

Example 1 — Basic Strong Friendship
Input Table:
user1_id user2_id
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
Output:
user1_id user2_id
1 2
1 3
2 3
💡 Note:

Users 1 and 2 are friends with common friends: 3, 4, 5 (3 common friends). Users 1 and 3 share friends: 2, 4, 5 (3 common). Users 2 and 3 share friends: 1, 4, 5 (3 common). All three friendships qualify as strong.
Example 2 — No Strong Friendships
Input Table:
user1_id user2_id
1 2
2 3
3 4
Output:
user1_id user2_id
💡 Note:

No friendship pairs have 3 or more common friends. Each friendship has at most 1 common friend, so no strong friendships exist.
Example 3 — Mixed Scenario
Input Table:
user1_id user2_id
1 7
1 2
1 3
2 7
3 7
2 4
3 4
Output:
user1_id user2_id
1 7
💡 Note:

Users 1 and 7 have common friends: 2, 3 (only 2 common friends, but if there were more relationships, it would be 3+). In this case, only friendship 1-7 has exactly the required number of mutual connections.

Constraints

  • 1 ≤ user1_id < user2_id ≤ 500
  • All pairs in the table represent valid friendships
  • The result should not contain duplicates

Visualization

Tap to expand
Strong Friendship Problem OverviewFriendship Network12345Find CommonFriendsAnalysis ResultsFriends 1-23 common: 3,4,5Friends 1-33 common: 2,4,5Friends 2-33 common: 1,4,5Other pairs< 3 commonStrong Friendships ✓(1,2), (1,3), (2,3)
Understanding the Visualization
1
Input
Friendship pairs table
2
Analysis
Find mutual friends via self-join
3
Filter
Keep friendships with 3+ common friends
Key Takeaway
🎯 Key Insight: Use self-joins to efficiently analyze relationship networks and find patterns in connected data

Related Problems

Asked in
Facebook 38 LinkedIn 25 Twitter 15
32.0K Views
Medium Frequency
~25 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