Friend Requests II: Who Has the Most Friends

medium database sql

Problem

RequestAccepted(requester_id, accepter_id, accept_date). Return the user id with the most friends and that count.

Inputr=[(1,2,'a'),(1,3,'b'),(2,3,'c'),(3,4,'d')]

Output(3, 3)

User 3 is connected to 1, 2, 4 — three friends.

rows (compact)

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

Explanation

A friendship is recorded as one row with a requester and an accepter, but friendship goes both ways — each person in the row gains one friend. So to count friends, both columns matter equally.

The trick is to stack both columns into a single list of ids. The inner query selects requester_id from every row and then UNION ALL with accepter_id from every row. Now each appearance of a person, whether as requester or accepter, is one entry.

We GROUP BY id and COUNT(*) to get each person's number of friends, then ORDER BY num DESC and LIMIT 1 to keep only the most-connected one.

Example: with rows (1,2),(1,3),(2,3),(3,4), id 3 shows up in three of them (as accepter twice and requester once), so it wins with a count of 3.

Time: O(n) Space: O(n)