LeetCode 3058 - Friends With No Mutual Friends

LeetCode Problem 3058

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The Friends table represents an undirected friendship graph. Each row (user_id1, user_id2) means the two users are directly connected as friends. The problem asks us to find every friendship pair where the two users do not share any common friend.

A mutual friend is a third user who is connected to both people in the pair. For example, if users 1 and 2 are friends, and both are also friends with user 5, then 5 is a mutual friend of 1 and 2.

The important detail is that we only care about pairs that already exist in the Friends table. We are not trying to generate all possible user pairs. Instead, for every friendship edge already present, we check whether the two endpoints have an intersection in their friend lists.

The input guarantees that (user_id1, user_id2) is unique. Since friendships are mutual, the relationship is conceptually undirected, even though only one ordered row is stored.

The expected output is every friendship pair that has zero mutual friends, sorted by user_id1 and then user_id2.

A few important observations and edge cases emerge immediately:

• Two users may have many friends, making naive comparison expensive.
• A pair with no other connected users should always qualify.
• Cycles in the friendship graph create mutual friends naturally.
• Dense friendship networks can create many overlapping friend sets.
• Since the friendship relation is undirected, we must treat (a, b) and (b, a) as equivalent.

The key challenge is efficiently determining whether two connected users share any neighbor.

Approaches

Brute Force Approach

The brute force solution examines every friendship pair individually. For each pair (u, v), we gather all friends of u and all friends of v, then compare them to determine whether a common user exists.

One straightforward implementation is:

1. Build an adjacency list for every user.
2. For each friendship pair:

• Iterate through all friends of u
• For each friend, check whether it also belongs to v's friend list

This approach is correct because it explicitly checks whether the intersection of the two friend sets is empty.

However, the runtime becomes expensive when users have many friends. In a dense graph, each friendship may require scanning large adjacency lists, leading to poor performance.

Optimal Approach

The key observation is that mutual friendships naturally appear as paths of length two.

Suppose we have:

• (u, x)
• (v, x)

Then x is a mutual friend of u and v.

Instead of checking every pair independently, we can directly generate all friendship pairs that do have mutual friends. After identifying them, we simply exclude those pairs from the final result.

This can be done efficiently using a self join on the Friends table:

• Join rows where two users share the same friend
• Normalize pair ordering with LEAST() and GREATEST()
• Collect all pairs that have at least one mutual friend
• Return friendship pairs not present in that set

This transforms the problem into a set exclusion operation, which databases handle efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(E × D)	O(V + E)	For each friendship, scan adjacency lists
Optimal	O(E²) worst case	O(E)	Uses joins to directly detect mutual friendships

Here:

• V is the number of users
• E is the number of friendships
• D is the average degree of a node

In practice, the SQL join based approach is significantly cleaner and more efficient for relational databases.

Algorithm Walkthrough

1. Treat the friendship table as an undirected graph.

Every row (user_id1, user_id2) represents a bidirectional friendship. Conceptually, both users belong to each other's friend lists. 2. Find all pairs that share a mutual friend.

We perform a self join on the Friends table. Suppose:

• Row f1 contains (a, x)
• Row f2 contains (b, x)

Then x is a common friend of a and b. 3. Normalize pair ordering.

Since friendships are undirected, (1, 2) and (2, 1) represent the same pair.

We use:

LEAST(a, b)
GREATEST(a, b)

to ensure consistent ordering. 4. Exclude identical users.

During the self join, we may accidentally produce (u, u). Those are invalid and must be removed. 5. Store all friendship pairs that have at least one mutual friend.

This set represents all pairs we must exclude from the answer. 6. Return original friendship rows not present in the exclusion set.

Every remaining pair is a friendship with zero mutual friends. 7. Sort the result.

The output must be ordered by user_id1 and user_id2.

Why it works

The algorithm relies on a fundamental graph property:

Two users have a mutual friend if and only if there exists some third user connected to both of them.

The self join enumerates exactly these situations. By collecting all friendship pairs that participate in at least one such configuration, we precisely identify every invalid pair. Subtracting them from the original friendships leaves only friendships with no mutual friends.

Python Solution

from typing import List

class Solution:
    def friendsWithNoMutualFriends(self, friends: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict

        # Build adjacency sets
        adjacency = defaultdict(set)

        for user1, user2 in friends:
            adjacency[user1].add(user2)
            adjacency[user2].add(user1)

        result = []

        for user1, user2 in friends:
            # Check whether the friend sets intersect
            has_mutual = False

            # Iterate through smaller set for efficiency
            if len(adjacency[user1]) > len(adjacency[user2]):
                user1, user2 = user2, user1

            for friend in adjacency[user1]:
                if friend != user2 and friend in adjacency[user2]:
                    has_mutual = True
                    break

            if not has_mutual:
                result.append([min(user1, user2), max(user1, user2)])

        result.sort()

        return result

The implementation begins by constructing an adjacency set for every user. A set is used because membership checks are O(1) on average, which makes mutual friend detection efficient.

For each friendship pair, the algorithm checks whether the two users share any common neighbor. To reduce unnecessary work, it iterates through the smaller adjacency set and tests membership in the larger one.

The condition:

friend != user2

ensures that we do not incorrectly treat the direct friendship itself as a mutual friend.

If no shared friend is found, the pair is added to the result.

Finally, the output is sorted to satisfy the required ordering.

Go Solution

package main

import (
	"sort"
)

type Solution struct{}

func (s Solution) friendsWithNoMutualFriends(friends [][]int) [][]int {
	adjacency := make(map[int]map[int]bool)

	// Build adjacency sets
	for _, edge := range friends {
		u := edge[0]
		v := edge[1]

		if adjacency[u] == nil {
			adjacency[u] = make(map[int]bool)
		}

		if adjacency[v] == nil {
			adjacency[v] = make(map[int]bool)
		}

		adjacency[u][v] = true
		adjacency[v][u] = true
	}

	result := [][]int{}

	for _, edge := range friends {
		u := edge[0]
		v := edge[1]

		hasMutual := false

		// Iterate through smaller adjacency set
		if len(adjacency[u]) > len(adjacency[v]) {
			u, v = v, u
		}

		for friend := range adjacency[u] {
			if friend != v && adjacency[v][friend] {
				hasMutual = true
				break
			}
		}

		if !hasMutual {
			a := u
			b := v

			if a > b {
				a, b = b, a
			}

			result = append(result, []int{a, b})
		}
	}

	sort.Slice(result, func(i, j int) bool {
		if result[i][0] == result[j][0] {
			return result[i][1] < result[j][1]
		}
		return result[i][0] < result[j][0]
	})

	return result
}

The Go implementation mirrors the Python logic closely.

Since Go does not have a built in hash set type, map[int]bool is used to simulate adjacency sets. Nil maps must be initialized before insertion, so each user's adjacency map is created lazily.

Sorting is implemented with sort.Slice, using lexicographical comparison on the pair values.

Go integers are sufficient for this problem, so overflow concerns are not relevant here.

Worked Examples

Example 1

Input:

[[1,2],[2,3],[2,4],[1,5],[6,7],[3,4],[2,5],[8,9]]

Step 1, Build adjacency sets

User	Friends
1	{2,5}
2	{1,3,4,5}
3	{2,4}
4	{2,3}
5	{1,2}
6	{7}
7	{6}
8	{9}
9	{8}

Step 2, Evaluate each friendship

Pair	Shared Friend?	Result
(1,2)	5	Exclude
(2,3)	4	Exclude
(2,4)	3	Exclude
(1,5)	2	Exclude
(6,7)	None	Include
(3,4)	2	Exclude
(2,5)	1	Exclude
(8,9)	None	Include

Final output:

[[6,7],[8,9]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E × D)	Each friendship checks overlapping neighbors
Space	O(V + E)	Adjacency sets store the graph

The adjacency structure requires storage proportional to the number of users and friendships.

For each friendship edge, we may scan the smaller adjacency set. If the average degree is D, the total runtime becomes approximately O(E × D).

In sparse graphs, this performs very efficiently. In dense graphs, the worst case approaches quadratic behavior.

Test Cases

from typing import List

class Solution:
    def friendsWithNoMutualFriends(self, friends: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict

        adjacency = defaultdict(set)

        for u, v in friends:
            adjacency[u].add(v)
            adjacency[v].add(u)

        result = []

        for u, v in friends:
            has_mutual = False

            a, b = u, v

            if len(adjacency[a]) > len(adjacency[b]):
                a, b = b, a

            for friend in adjacency[a]:
                if friend != b and friend in adjacency[b]:
                    has_mutual = True
                    break

            if not has_mutual:
                result.append([min(u, v), max(u, v)])

        result.sort()

        return result

solver = Solution()

# Provided example
assert solver.friendsWithNoMutualFriends([
    [1,2],[2,3],[2,4],[1,5],
    [6,7],[3,4],[2,5],[8,9]
]) == [[6,7],[8,9]]  # mixed graph with valid and invalid pairs

# Single friendship
assert solver.friendsWithNoMutualFriends([
    [1,2]
]) == [[1,2]]  # no possible mutual friends

# Triangle graph
assert solver.friendsWithNoMutualFriends([
    [1,2],[2,3],[1,3]
]) == []  # every pair has a mutual friend

# Disconnected components
assert solver.friendsWithNoMutualFriends([
    [1,2],[3,4]
]) == [[1,2],[3,4]]  # isolated edges

# Chain graph
assert solver.friendsWithNoMutualFriends([
    [1,2],[2,3],[3,4]
]) == [[1,2],[2,3],[3,4]]  # no triangles exist

# Square cycle without diagonals
assert solver.friendsWithNoMutualFriends([
    [1,2],[2,3],[3,4],[4,1]
]) == [[1,2],[1,4],[2,3],[3,4]]  # cycle without shared neighbors

# Dense clique
assert solver.friendsWithNoMutualFriends([
    [1,2],[1,3],[1,4],
    [2,3],[2,4],[3,4]
]) == []  # every pair shares multiple friends

Test	Why
Provided example	Validates mixed inclusion and exclusion
Single friendship	Smallest valid input
Triangle graph	Every pair has a mutual friend
Disconnected components	Independent edges should remain
Chain graph	Verifies absence of triangles
Square cycle	Ensures cycles alone do not imply mutual friends
Dense clique	Stress case with maximum overlap

Edge Cases

Single Isolated Friendship

If the graph contains only one friendship pair, there cannot possibly be a mutual friend because no third user exists.

A naive implementation might accidentally treat the connected user itself as a mutual connection. The implementation avoids this by explicitly excluding the direct partner during intersection checks.

Triangle Structures

A triangle such as:

1 - 2
 \ /
  3

creates a mutual friend for every edge. This is the most important structural pattern in the problem.

Incorrect implementations sometimes only check one direction of adjacency or fail to normalize undirected relationships properly. Using bidirectional adjacency sets guarantees accurate detection.

Dense Friendship Networks

In a clique, every user connects to every other user. Every friendship therefore has many mutual friends.

This stresses both correctness and performance. The implementation handles it correctly because it terminates early once a single shared friend is found, avoiding unnecessary scanning.

Disconnected Components

The graph may contain completely unrelated groups of users.

The algorithm naturally handles this because adjacency sets are local to each connected component. Users from different components never appear during intersection checks.