Problem

Table: RequestAccepted

1
2
3
4
5
6
7
8
9

+----------------+---------+
| Column Name | Type |
+----------------+---------+
| requester_id | int |
| accepter_id | int |
| accept_date | date |
+----------------+---------+
(requester_id, accepter_id) is the primary key (combination of columns with unique values) for this table.
This table contains the ID of the user who sent the request, the ID of the user who received the request, and the date when the request was accepted.

Write a solution to find the people who have the most friends and the most friends number.

The test cases are generated so that only one person has the most friends.

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

Input: 
RequestAccepted table:
+--------------+-------------+-------------+
| requester_id | accepter_id | accept_date |
+--------------+-------------+-------------+
| 1            | 2           | 2016/06/03  |
| 1            | 3           | 2016/06/08  |
| 2            | 3           | 2016/06/08  |
| 3            | 4           | 2016/06/09  |
+--------------+-------------+-------------+
Output: 
+----+-----+
| id | num |
+----+-----+
| 3  | 3   |
+----+-----+
Explanation: 
The person with id 3 is a friend of people 1, 2, and 4, so he has three friends in total, which is the most number than any others.

Follow up: In the real world, multiple people could have the same most number of friends. Could you find all these people in this case?

Solution

Method 1 – Union and Aggregation

Intuition

A friendship is bidirectional, so both requester and accepter become friends. We can count the number of unique friends for each user by combining both columns and aggregating.

Approach

  1. For each row, treat both requester and accepter as friends of each other.
  2. Use a union to create a list of (user, friend) pairs in both directions.
  3. Count the number of unique friends for each user.
  4. Find the user with the maximum number of friends.
  5. Return the user id and the number of friends.

Code

1
2
3
4
5
6
7
8
9

SELECT user_id, COUNT(DISTINCT friend_id) AS num
FROM (
  SELECT requester_id AS user_id, accepter_id AS friend_id FROM RequestAccepted
  UNION ALL
  SELECT accepter_id, requester_id FROM RequestAccepted
) t
GROUP BY user_id
ORDER BY num DESC
LIMIT 1;
1
2
3
4
5
6
7
8
9

SELECT user_id, COUNT(DISTINCT friend_id) AS num
FROM (
  SELECT requester_id AS user_id, accepter_id AS friend_id FROM RequestAccepted
  UNION ALL
  SELECT accepter_id, requester_id FROM RequestAccepted
) t
GROUP BY user_id
ORDER BY num DESC
LIMIT 1;
1
2
3
4
5
6
7
8
9

class Solution:
    def most_friends(self, df: 'pd.DataFrame') -> 'pd.DataFrame':
        import pandas as pd
        a = df[['requester_id', 'accepter_id']].rename(columns={'requester_id': 'user_id', 'accepter_id': 'friend_id'})
        b = df[['accepter_id', 'requester_id']].rename(columns={'accepter_id': 'user_id', 'requester_id': 'friend_id'})
        all_friends = pd.concat([a, b])
        cnt = all_friends.groupby('user_id')['friend_id'].nunique().reset_index(name='num')
        max_num = cnt['num'].max()
        return cnt[cnt['num'] == max_num].reset_index(drop=True)

Complexity

  • ⏰ Time complexity: O(n), where n is the number of rows in the table, since each row is processed twice.
  • 🧺 Space complexity: O(n), for storing the expanded friend pairs.