{x}
blog image

Friend Requests II: Who Has the Most Friends

Table: RequestAccepted

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

 

Example 1:

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 Explanation: Finding the Person with the Most Friends

This problem requires finding the person with the most friends based on the RequestAccepted table. The table only shows accepted friend requests; we need to consider both requester_id and accepter_id as friends for each entry.

Approach

The solution uses a SQL query with a common table expression (CTE) to efficiently solve this. Here's a breakdown:

  1. Unioning Friend Relationships: A CTE T is created using UNION ALL. This combines two SELECT statements:

    • The first selects requester_id and accepter_id directly from RequestAccepted, representing one direction of the friendship.
    • The second selects accepter_id and requester_id, reversing the order to capture the other direction of the friendship. This ensures that both sides of a friendship are counted.

  2. Counting Friendships: The main query then uses T to count the number of friends for each person. GROUP BY requester_id groups the results by person, and COUNT(1) counts the number of entries for each person. This represents their number of friends.

  3. Ordering and Limiting Results: ORDER BY 2 DESC orders the results in descending order based on the count of friends (the second column). LIMIT 1 restricts the output to only the top row, which contains the person with the most friends.

  4. Renaming Columns: Finally, requester_id AS id and COUNT(1) AS num rename the columns for clarity.

MySQL Code

WITH
    T AS (
        SELECT requester_id, accepter_id FROM RequestAccepted
        UNION ALL
        SELECT accepter_id, requester_id FROM RequestAccepted
    )
SELECT requester_id AS id, COUNT(1) AS num
FROM T
GROUP BY 1
ORDER BY 2 DESC
LIMIT 1;

Time and Space Complexity Analysis

  • Time Complexity: The UNION ALL operation takes O(N) time, where N is the number of rows in RequestAccepted. The GROUP BY operation also takes O(N) time in the average case. The sorting (ORDER BY) is O(N log N) in the average case for most database systems. The LIMIT 1 operation takes constant time O(1). Therefore, the overall time complexity is dominated by the sorting, making it O(N log N).

  • Space Complexity: The space complexity is primarily determined by the size of the CTE T, which is O(N) in the worst case (all requests are unique). The space for the final result is constant, O(1). Hence the overall space complexity is O(N).

Note: The actual performance might vary depending on the specific database system's optimization techniques and the size of the input data. The complexities given are based on a general analysis of the algorithm.