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

This chapter tackles LeetCode 602 ("Friend Requests II: Who Has the Most Friends"), focusing on advanced relational aggregation, combining bi-directional graph connections using UNION ALL, and isolating top-ranked records using SQL grouping and ordering techniques.

1. Problem Statement & Schema Overview

In social network databases, friendship is typically a two-way (undirected) relationship. When User A sends a friend request to User B and User B accepts it, both users gain a friend.

We are given a table named RequestAccepted with the following schema:

• Primary Key: The combination of (requester_id, acceptor_id) acts as the composite primary key.
• Objective: Write a SQL query to find the ID of the person who has the most friends and the corresponding total number of friends.
• Assumption: Test cases are generated such that exactly one person has the maximum number of friends (no ties).

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: The Party Invitation List

Imagine tracking social connections at a party. Every time Person A and Person B agree to be friends, their names are written down in a logbook.

• If User 1 sends a request to User 2, User 1's name appears in the requester column, and User 2's name appears in the acceptor column.
• To find out how many total friends User 1 has, we cannot just look at who they sent requests to; we must also count how many requests they accepted from others.

Therefore, a user's total friend count is equal to the total number of times their ID appears across both columns (requester_id and acceptor_id).

3. Sample Data Walkthrough

Consider the following sample RequestAccepted table:

Let us trace how each user accumulates friends row by row:

1. Row 1 (1 sends to 2):
   • User 1 gets 1 friend (Total: 1)
   • User 2 gets 1 friend (Total: 1)
2. Row 2 (1 sends to 3):
   • User 1 gets another friend (Total: 2)
   • User 3 gets 1 friend (Total: 1)
3. Row 3 (2 sends to 3):
   • User 2 gets another friend (Total: 2)
   • User 3 gets another friend (Total: 2)
4. Row 4 (3 sends to 4):
   • User 3 gets another friend (Total: 3)
   • User 4 gets 1 friend (Total: 1)

Final Tally:

• User 1: 2 friends
• User 2: 2 friends
• User 3: 3 friends (Maximum)
• User 4: 1 friend

Expected Output:

4. Step-by-Step Solution Evolution

To solve this problem efficiently in MySQL, we break the query down into three logical phases:

1. Unifying both columns using UNION ALL to list every user appearance.
2. Aggregating and counting occurrences per user ID using GROUP BY and COUNT().
3. Sorting and limiting to isolate the single user with the maximum friends.

5. Phase 1: Combining Requesters and Acceptors (UNION ALL)

Because a user can appear in either the requester_id column or the acceptor_id column, we must stack these two columns on top of each other.

Note: We use UNION ALL instead of UNION. UNION automatically eliminates duplicate rows, which would destroy our count frequency. UNION ALL preserves all rows (including duplicates), which is critical because a user's frequency of appearance equals their total friend count.

SQL Implementation (Step 1)

SELECT requester_id AS id 
FROM RequestAccepted

UNION ALL

SELECT acceptor_id AS id 
FROM RequestAccepted;

Intermediate Result:

Running this subquery produces a single list of all user IDs involved in any friendship transaction:

Notice how ID 1 appears twice, ID 2 appears twice, ID 3 appears three times, and ID 4 appears once.

6. Phase 2: Aggregating Friend Counts (GROUP BY)

Now that all IDs are unified into a single virtual table, we treat this result set as a derived table (subquery) and apply aggregation. We group by id and count how many times each ID appears.

SQL Implementation (Step 2)

SELECT id, COUNT(*) AS num
FROM (
    SELECT requester_id AS id FROM RequestAccepted
    UNION ALL
    SELECT acceptor_id AS id FROM RequestAccepted
) AS friend_count
GROUP BY id;

Crucial SQL Rule: In MySQL, every derived table used in a FROM clause must be given an alias (e.g., AS friend_count). Omitting this alias will throw a syntax error.

Intermediate Result:

7. Phase 3: Finding the Maximum (ORDER BY & LIMIT)

We now have each user paired with their total friend count. To find the user with the most friends, we sort the result set in descending order based on num and use LIMIT 1 to pick the top record.

Final Production SQL Query

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

8. Summary and Key Takeaways

• Bi-Directional Graph Modeling: Social network tables store relationships across two columns (requester_id and acceptor_id). Both columns must be queried to capture total connections.
• UNION vs. UNION ALL: Always use UNION ALL when calculating frequencies or counts, because standard UNION strips duplicate rows.
• Derived Table Aliasing: In SQL, subqueries placed in the FROM clause require an explicit alias (e.g., AS friend_count), or the query engine will throw an error.
• Aggregation with GROUP BY: Grouping by id combined with COUNT(*) transforms raw transaction rows into metrics per user.
• Top-N Filtering: Use ORDER BY ... DESC paired with LIMIT 1 to efficiently extract the single highest-ranking record in single-winner scenarios.