LeetCode 1949 - Strong Friendship

LeetCode Problem 1949

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem gives us a table named Friendship, where every row represents a friendship relationship between two users. Each friendship is stored only once because the problem guarantees that user1_id < user2_id.

We are asked to identify all pairs of users whose friendship is considered "strong". A friendship between users x and y is strong if they share at least three mutual friends.

A mutual friend is a user who is directly connected to both x and y.

For example, if:

User 1 is friends with 3, 4, 5, and 6
User 2 is also friends with 3, 4, 5, and 6

then users 1 and 2 have four common friends, so their friendship is strong.

The output must contain:

user1_id
user2_id
common_friend, which is the number of mutual friends

The result should contain only valid friendships that already exist in the table. This is important because two users may share many common friends without being directly connected themselves.

The input guarantees:

Every friendship pair is unique
user1_id < user2_id
Friendships are undirected relationships

This means friendship (1,2) is the same as (2,1), even though only one direction is stored.

The main challenge is efficiently counting common friends between existing friendship pairs.

A naive implementation could become very expensive because checking every possible pair of users and comparing friend lists repeatedly would involve many redundant computations.

Important edge cases include:

Friendships with exactly three common friends, these must be included
Users with no shared friends
Sparse graphs where most users have very few friendships
Dense graphs where many users are connected to each other
Duplicate counting caused by the undirected nature of friendships

The problem guarantees there are no duplicate friendship rows, which simplifies handling symmetric relationships.

Approaches

Brute Force Approach

The brute force approach is to examine every friendship pair individually and explicitly compute the intersection of their friend lists.

First, we build an adjacency list where each user maps to all of their friends.

Then, for every friendship (u, v):

Retrieve all friends of u
Retrieve all friends of v
Count how many users appear in both sets
If the count is at least three, include the pair in the result

This works because the definition of a strong friendship depends entirely on the number of shared neighbors in the friendship graph.

However, this approach can become expensive when users have many friends. If two users each have large friend lists, repeatedly intersecting large sets for every friendship pair leads to substantial overhead.

Optimal Approach

The key insight is that common friendships can be generated directly through self joins.

Suppose user f is a mutual friend of both u and v.

Then there must exist:

friendship (u, f)
friendship (v, f)

If we enumerate all such combinations, we can directly generate pairs of users sharing a mutual friend.

This transforms the problem into counting how many times each user pair appears as a shared connection.

In SQL, this is naturally solved using a self join on the friendship table.

The process becomes:

Expand friendships into an undirected representation
Join the friendship table with itself on the common friend
Generate user pairs sharing the same friend
Count occurrences
Keep only pairs with count at least 3
Ensure the pair itself is an existing friendship

This avoids repeatedly intersecting large sets and leverages SQL's grouping and aggregation efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(F × D) to O(F × D²)	O(F)	Repeatedly intersects friend lists
Optimal	O(F²) worst case	O(F)	Uses joins and aggregation efficiently

Here:

F = number of friendships
D = average degree of a user

Algorithm Walkthrough

First, convert the friendship table into an undirected representation.

Since the table stores only (u, v) where u < v, we create both directions:

(u, v)
(v, u)

This makes it easy to look up all friends of a user uniformly. 2. Perform a self join on the undirected friendship table.

Suppose:

(a.user_id, a.friend_id)
(b.user_id, b.friend_id)

If a.friend_id = b.friend_id, then both users share the same mutual friend. 3. Ensure the user pair is ordered consistently.

We enforce:

a.user_id < b.user_id

This prevents duplicate counting such as both (1,2) and (2,1). 4. Group by the user pair.

Every matching row from the self join corresponds to one shared friend.

By grouping:

GROUP BY a.user_id, b.user_id

we can count the number of common friends. 5. Keep only pairs with at least three common friends.

This is done using:

HAVING COUNT(*) >= 3

Verify the pair itself is an actual friendship.

The problem asks for strong friendships, not merely pairs with many common friends.

Therefore, we join back to the original friendship table to ensure the pair exists.

Why it works

The algorithm works because every common friend contributes exactly one matching row in the self join.

If users u and v both connect to user f, then the join produces one row representing that shared friend.

Grouping all such rows together gives the exact number of common friends between u and v.

Because we enforce u < v, every pair is counted exactly once.

Finally, joining back to the original friendship table guarantees we return only actual friendships.

Python Solution

# Write your MySQL query statement below

SELECT
    f.user1_id,
    f.user2_id,
    COUNT(*) AS common_friend
FROM
(
    SELECT user1_id AS user_id, user2_id AS friend_id
    FROM Friendship

    UNION ALL

    SELECT user2_id AS user_id, user1_id AS friend_id
    FROM Friendship
) a
JOIN
(
    SELECT user1_id AS user_id, user2_id AS friend_id
    FROM Friendship

    UNION ALL

    SELECT user2_id AS user_id, user1_id AS friend_id
    FROM Friendship
) b
ON a.friend_id = b.friend_id
AND a.user_id < b.user_id
JOIN Friendship f
ON f.user1_id = a.user_id
AND f.user2_id = b.user_id
GROUP BY f.user1_id, f.user2_id
HAVING COUNT(*) >= 3;

The solution begins by constructing an undirected version of the friendship graph. Since the original table stores only one direction of each friendship, we use UNION ALL to add the reverse direction.

After that, we perform a self join on the shared friend identifier. This allows us to generate all pairs of users who share a common friend.

The condition:

a.user_id < b.user_id

ensures that every pair appears only once.

Next, we join the generated user pair back to the original friendship table. This step guarantees that the pair itself is directly connected.

Finally, we group by the friendship pair and count how many shared friends exist. The HAVING clause filters out pairs with fewer than three common friends.

Go Solution

// Write your MySQL query statement below

SELECT
    f.user1_id,
    f.user2_id,
    COUNT(*) AS common_friend
FROM
(
    SELECT user1_id AS user_id, user2_id AS friend_id
    FROM Friendship

    UNION ALL

    SELECT user2_id AS user_id, user1_id AS friend_id
    FROM Friendship
) a
JOIN
(
    SELECT user1_id AS user_id, user2_id AS friend_id
    FROM Friendship

    UNION ALL

    SELECT user2_id AS user_id, user1_id AS friend_id
    FROM Friendship
) b
ON a.friend_id = b.friend_id
AND a.user_id < b.user_id
JOIN Friendship f
ON f.user1_id = a.user_id
AND f.user2_id = b.user_id
GROUP BY f.user1_id, f.user2_id
HAVING COUNT(*) >= 3;

Because this is a database problem, the submission language does not actually change the implementation. LeetCode expects a SQL query regardless of the selected language section.

The logic remains identical across both sections.

Worked Examples

Example 1

Input:

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

Step 1: Build Undirected Friendships

user_id	friend_id
1	2
2	1
1	3
3	1
2	3
3	2
...	...

Every friendship appears in both directions.

Step 2: Self Join on Common Friend

Suppose common friend = 3.

Users connected to 3:

This generates pair (1,2).

Suppose common friend = 4.

Users connected to 4:

Again generates (1,2).

Suppose common friend = 6.

Users connected to 6:

Generated pairs:

(1,2)
(1,3)
(2,3)

Step 3: Aggregate Counts

Pair	Common Friends
(1,2)	4
(1,3)	3
(2,3)	2

Step 4: Filter by Count >= 3

Remaining pairs:

user1_id	user2_id	common_friend
1	2	4
1	3	3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(F²) worst case	Self joins may compare many friendship pairs
Space	O(F)	Temporary join/grouping structures

The dominant operation is the self join on the undirected friendship table.

In sparse friendship graphs, performance is typically much better than the worst case because relatively few users share the same mutual friend.

The query also benefits from SQL engine optimizations such as indexing and hash aggregation.

Test Cases

# Example case from the problem
# (1,2) has 4 common friends
# (1,3) has 3 common friends

friendships = [
    [1,2],
    [1,3],
    [2,3],
    [1,4],
    [2,4],
    [1,5],
    [2,5],
    [1,7],
    [3,7],
    [1,6],
    [3,6],
    [2,6]
]

# Expected:
# [1,2,4]
# [1,3,3]

# Exactly three common friends
friendships = [
    [1,2],
    [1,3],
    [2,3],
    [1,4],
    [2,4],
    [1,5],
    [2,5]
]

# Expected:
# [1,2,3]

# Fewer than three common friends
friendships = [
    [1,2],
    [1,3],
    [2,3]
]

# Expected:
# empty result

# Dense graph
friendships = [
    [1,2],
    [1,3],
    [1,4],
    [1,5],
    [2,3],
    [2,4],
    [2,5],
    [3,4],
    [3,5],
    [4,5]
]

# Many pairs should qualify

# Disconnected components
friendships = [
    [1,2],
    [1,3],
    [2,3],
    [4,5],
    [4,6],
    [5,6]
]

# Expected:
# empty result

# Pair with many common friends but no direct friendship
friendships = [
    [1,3],
    [2,3],
    [1,4],
    [2,4],
    [1,5],
    [2,5]
]

# (1,2) has 3 common friends
# but there is no direct friendship (1,2)
# Expected:
# empty result

Test	Why
Problem example	Validates standard functionality
Exactly three common friends	Ensures boundary condition is included
Fewer than three common friends	Ensures filtering works correctly
Dense graph	Tests many overlapping friendships
Disconnected components	Ensures unrelated groups do not interfere
No direct friendship	Confirms final friendship validation step

Edge Cases

Exactly Three Common Friends

A very common off by one mistake is using > instead of >=.

If two users share exactly three mutual friends, the friendship must still be considered strong.

The implementation handles this correctly using:

HAVING COUNT(*) >= 3

Shared Friends Without Direct Friendship

Two users may share many common friends without actually being directly connected.

For example:

(1,3)
(2,3)
(1,4)
(2,4)
(1,5)
(2,5)

Users 1 and 2 share three mutual friends but are not themselves friends.

The join back to the original Friendship table prevents such invalid pairs from appearing in the result.

Duplicate Pair Generation

Because friendships are undirected, a naive self join could generate both:

(1,2)
(2,1)

This would cause duplicate counting and duplicate output rows.

The implementation avoids this by enforcing:

a.user_id < b.user_id

This guarantees each pair is processed exactly once.