LeetCode 602: Friend Requests II: Who Has the Most Friends

Problem Restatement

We are given a table called RequestAccepted.

Each row means one friend request was accepted.

We need to find the user who has the most friends and return:

The test cases guarantee that only one person has the most friends. The problem also asks a follow-up where multiple people may tie for the most friends. The main solution only needs to return one user because the official test cases guarantee a unique answer. Source

Input and Output

Input table:

RequestAccepted

Output columns:

id, num

Each accepted request creates one friendship between two users.

So if this row exists:

requester_id = 1, accepter_id = 2

then user 1 has user 2 as a friend, and user 2 has user 1 as a friend.

Both sides must be counted.

Example

Input:

Friend counts:

User 3 has the most friends.

Output:

First Thought: Count Requesters Only

A first attempt might count how many times each user appears in requester_id.

SELECT requester_id, COUNT(*)
FROM RequestAccepted
GROUP BY requester_id;

This is incomplete.

A user can have friends from both sides of the table:

Both roles represent friendship.

So we need to count every appearance of a user in either column.

Key Insight

Each accepted request contributes one friend count to both users.

For this row:

we should count:

The clean way is to convert both columns into one column named id.

We can do that with UNION ALL.

SELECT requester_id AS id
FROM RequestAccepted

UNION ALL

SELECT accepter_id AS id
FROM RequestAccepted

After this transformation, each row means:

“This user has one friend contribution.”

Then we group by id and count rows.

Algorithm

First, select all requesters as user ids.

Second, select all accepters as user ids.

Third, combine them with UNION ALL.

Fourth, group by user id and count how many times each user appears.

Fifth, sort by the count in descending order.

Finally, return the first row.

SQL Solution

SELECT
    id,
    COUNT(*) AS num
FROM (
    SELECT requester_id AS id
    FROM RequestAccepted

    UNION ALL

    SELECT accepter_id AS id
    FROM RequestAccepted
) AS friends
GROUP BY id
ORDER BY num DESC
LIMIT 1;

Code Explanation

The inner query creates one unified list of user ids:

SELECT requester_id AS id
FROM RequestAccepted

UNION ALL

SELECT accepter_id AS id
FROM RequestAccepted

We use UNION ALL, not UNION.

UNION ALL keeps every row. That matters because every accepted request contributes to the friend count.

If user 3 appears three times across both columns, we need all three appearances to remain.

The outer query groups the unified list:

GROUP BY id

Then it counts how many rows each user has:

COUNT(*) AS num

This count is the total number of friends for that user.

Then we sort from largest to smallest:

ORDER BY num DESC

Because the problem guarantees one unique user with the most friends, we can return only the first row:

LIMIT 1

Correctness

Each row in RequestAccepted represents one accepted friendship between requester_id and accepter_id.

The inner query emits one row for the requester and one row for the accepter. Therefore, each friendship contributes exactly one count to each of its two users.

After the UNION ALL, every emitted row represents one friend contribution for one user.

The outer query groups these contributions by user id. Therefore, COUNT(*) gives the total number of friends for each user.

Sorting by this count in descending order places the user with the largest friend count first.

Since the test cases guarantee that only one person has the most friends, LIMIT 1 returns exactly the required user and friend count.

Complexity

Let n be the number of rows in RequestAccepted.

The derived table has 2n rows because every friendship contributes one row for each user.

Follow-up: Return All Ties

In the real world, multiple users may have the same maximum number of friends.

For that version, we can rank users by friend count and return every user whose rank is 1.

WITH friend_counts AS (
    SELECT
        id,
        COUNT(*) AS num
    FROM (
        SELECT requester_id AS id
        FROM RequestAccepted

        UNION ALL

        SELECT accepter_id AS id
        FROM RequestAccepted
    ) AS friends
    GROUP BY id
),
ranked AS (
    SELECT
        id,
        num,
        DENSE_RANK() OVER (ORDER BY num DESC) AS rnk
    FROM friend_counts
)
SELECT
    id,
    num
FROM ranked
WHERE rnk = 1;

Testing

Sample data:

CREATE TABLE RequestAccepted (
    requester_id INT,
    accepter_id INT,
    accept_date DATE
);

INSERT INTO RequestAccepted (requester_id, accepter_id, accept_date) VALUES
    (1, 2, '2016-06-03'),
    (1, 3, '2016-06-08'),
    (2, 3, '2016-06-08'),
    (3, 4, '2016-06-09');

Expected output:

Additional case:

TRUNCATE TABLE RequestAccepted;

INSERT INTO RequestAccepted (requester_id, accepter_id, accept_date) VALUES
    (1, 2, '2020-01-01'),
    (2, 3, '2020-01-02'),
    (2, 4, '2020-01-03');

Friend counts:

Expected output: