Watch the video solution for Strong Friendship, a medium level problem involving Database. This walkthrough by Everyday Data Science has 863 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Friendship
+-------------+------+ | Column Name | Type | +-------------+------+ | user1_id | int | | user2_id | int | +-------------+------+ (user1_id, user2_id) is the primary key (combination of columns with unique values) for this table. Each row of this table indicates that the 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 that the result table should not contain duplicates with user1_id < user2_id.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Friendship table: +----------+----------+ | user1_id | user2_id | +----------+----------+ | 1 | 2 | | 1 | 3 | | 2 | 3 | | 1 | 4 | | 2 | 4 | | 1 | 5 | | 2 | 5 | | 1 | 7 | | 3 | 7 | | 1 | 6 | | 3 | 6 | | 2 | 6 | +----------+----------+ Output: +----------+----------+---------------+ | user1_id | user2_id | common_friend | +----------+----------+---------------+ | 1 | 2 | 4 | | 1 | 3 | 3 | +----------+----------+---------------+ Explanation: Users 1 and 2 have 4 common friends (3, 4, 5, and 6). Users 1 and 3 have 3 common friends (2, 6, and 7). We did not include the friendship of users 2 and 3 because they only have two common friends (1 and 6).
Problem Overview: The Friendship table stores pairs of users who are friends. A pair forms a strong friendship if they are already friends and share at least three common friends. The task is to compute the number of mutual friends for each friendship pair and return those with at least three.
Approach 1: Self Join to Count Mutual Friends (O(F²) time, O(F) space)
The direct approach is to treat the friendship table as an undirected graph and join it with itself to discover mutual neighbors. First normalize friendships so each edge works in both directions (A → B and B → A). Then perform a self JOIN on the friend column to find users who share the same friend. Each match represents a mutual friend between two users. After that, group by the user pair and count the shared friends using COUNT(). Finally filter pairs where the count is at least three and ensure the pair itself exists in the original friendship table. This method relies heavily on SQL joins and aggregation, a common pattern in database and SQL interview problems.
Approach 2: Edge Normalization + Aggregation (O(F²) time, O(F) space)
A cleaner variation explicitly normalizes the friendship graph first. Use a UNION to create bidirectional edges so every friendship appears as both (A,B) and (B,A). This simplifies the logic because every user's friends can be treated uniformly. Then join the normalized table with itself on the shared friend column to identify candidate user pairs who share a mutual friend. Exclude identical users and aggregate using GROUP BY user1, user2. The mutual friend count is computed with COUNT(*), and a HAVING clause filters counts ≥ 3. Finally restrict results to pairs that are actual friends in the original table. This approach keeps the query easier to reason about when working with graph-like relationships in relational databases.
Both approaches rely on the same underlying idea: mutual friends appear when two users connect to the same third user. SQL expresses this naturally through self joins and GROUP BY. These techniques appear frequently in problems involving social graphs, recommendation systems, and co-occurrence analysis.
Recommended for interviews: The normalized edge + aggregation approach is usually preferred. It clearly models the social graph and avoids asymmetric edge issues. Interviewers expect you to recognize the pattern of converting relationships into bidirectional edges and then using a self join to compute mutual connections. Demonstrating the brute-force join idea shows understanding, but structuring the query cleanly with normalization reflects stronger SQL design skills, especially for database and SQL interview questions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self Join to Count Mutual Friends | O(F²) | O(F) | Direct SQL solution when analyzing mutual connections in a friendship graph |
| Edge Normalization + Aggregation | O(F²) | O(F) | Preferred when treating friendships as an undirected graph with cleaner query logic |
