Is Strong Friendship easy or hard?

Strong Friendship is considered a Medium database problem. The difficulty comes from recognizing that mutual friends can be computed using a self join and correctly filtering pairs that already exist as friendships.

Strong Friendship Python/Java solution

This problem is designed for SQL rather than general programming languages. The solution typically uses MySQL queries with self joins and GROUP BY to count mutual friends and filter pairs with at least three shared connections.

How to solve Strong Friendship in O(n)?

A pure O(n) solution is not typical in SQL because detecting mutual friends requires comparing friend lists between users. Most implementations rely on a self join that behaves closer to O(F²). Database indexing and query optimization can improve practical performance but not the theoretical join complexity.

What is the best approach for Strong Friendship?

The most practical approach uses SQL self joins with aggregation. Convert the friendship table into bidirectional edges, join the table with itself on the mutual friend column, and group by the user pair to count common friends. Filter with HAVING count >= 3 and ensure the pair exists in the original friendship table.

Is Strong Friendship asked at Google/Amazon/Meta?

Problems involving mutual connections and social graph analysis appear frequently in database and data engineering interviews at large tech companies. Variations of mutual friend counting and relationship joins have been reported in SQL interviews at companies like Amazon and Meta.

What data structure is used in Strong Friendship?

Conceptually the problem models a social graph where users are nodes and friendships are edges. In SQL this graph is represented using a relational table and processed with self joins, grouping, and aggregation to compute shared neighbors.

What is the time complexity of Strong Friendship?

The dominant cost comes from joining the friendship table with itself to find shared neighbors. This produces roughly O(F²) join complexity where F is the number of friendship records. Aggregation and filtering add smaller overhead.

1949. Strong Friendship - Practice Online

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).