All the Pairs With the Maximum Number of Common Followers

Problem

Table: Relations

1
2
3
4
5
6
7
8


    +-------------+------+
    | Column Name | Type |
    +-------------+------+
    | user_id     | int  |
    | follower_id | int  |
    +-------------+------+
    (user_id, follower_id) is the primary key (combination of columns with unique values) for this table.
    Each row of this table indicates that the user with ID follower_id is following the user with ID user_id.

Write a solution to find all the pairs of users with the maximum number of common followers. In other words, if the maximum number of common followers between any two users is maxCommon, then you have to return all pairs of users that have maxCommon common followers.

The result table should contain the pairs user1_id and user2_id where user1_id < user2_id.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


Input: 
Relations table:
+---------+-------------+
| user_id | follower_id |
+---------+-------------+
| 1       | 3           |
| 2       | 3           |
| 7       | 3           |
| 1       | 4           |
| 2       | 4           |
| 7       | 4           |
| 1       | 5           |
| 2       | 6           |
| 7       | 5           |
+---------+-------------+
Output: 
+----------+----------+
| user1_id | user2_id |
+----------+----------+
| 1        | 7        |
+----------+----------+
Explanation: 
Users 1 and 2 have two common followers (3 and 4).
Users 1 and 7 have three common followers (3, 4, and 5).
Users 2 and 7 have two common followers (3 and 4).
Since the maximum number of common followers between any two users is 3, we return all pairs of users with three common followers, which is only the pair (1, 7). We return the pair as (1, 7), not as (7, 1).
Note that we do not have any information about the users that follow users 3, 4, and 5, so we consider them to have 0 followers.

Solution

Method 1 – Using Self Join and Group By

Intuition

The key idea is to find all pairs of users who share the same followers. By joining the table with itself on follower_id, we can count how many followers two users have in common. Then, we select the pairs with the maximum count.

Approach

Perform a self-join on the Relations table using follower_id to find all pairs of users followed by the same follower.
Ensure user1_id < user2_id to avoid duplicate and reversed pairs.
Group by the user pairs and count the number of common followers for each pair.
Find the maximum number of common followers among all pairs.
Select all pairs whose count equals this maximum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


WITH CommonFollowers AS (
  SELECT
    r1.user_id AS user1_id,
    r2.user_id AS user2_id,
    COUNT(*) AS common_count
  FROM Relations r1
  JOIN Relations r2
    ON r1.follower_id = r2.follower_id
    AND r1.user_id < r2.user_id
  GROUP BY r1.user_id, r2.user_id
),
MaxCommon AS (
  SELECT MAX(common_count) AS max_common
  FROM CommonFollowers
)
SELECT user1_id, user2_id
FROM CommonFollowers, MaxCommon
WHERE common_count = max_common;

Complexity

⏰ Time complexity: O(n^2) (due to the self-join and grouping)
🧺 Space complexity: O(n^2) (for storing all user pairs and their common follower counts)

Problem#

Examples#

Solution#

Method 1 – Using Self Join and Group By#

Intuition#

Approach#

Code#

Complexity#