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

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem gives us a database table named RequestAccepted, where each row represents a successfully accepted friend request between two users. Every record contains a requester_id, an accepter_id, and the date the request was accepted.

The important detail is that friendship is mutual. If user 1 sends a friend request to user 2 and it is accepted, then both users become friends with each other. Therefore, each row contributes one friend to both the requester and the accepter.

The goal is to determine which person has the highest number of total friends and return both the user's ID and the number of friends they have.

For example, consider this relationship:

1 <-> 2
1 <-> 3
2 <-> 3
3 <-> 4

User 3 is connected to users 1, 2, and 4, so they have 3 friends total. No other user has as many friends, so the result is:

id = 3
num = 3

The table guarantees that (requester_id, accepter_id) is unique, which means the same accepted request cannot appear twice in the same direction. However, the problem does not explicitly guarantee that the reverse pair cannot appear separately, so a robust solution should still think carefully about counting logic.

The problem statement also guarantees that only one user has the maximum number of friends. The follow-up question removes this guarantee and asks how to return all users tied for the maximum.

An important observation is that we are not being asked to compute direct graph traversal or connected components. We only need the degree of each node in the friendship graph. Every accepted friendship contributes exactly one friend count to both involved users.

Several edge cases are worth considering:

A user may appear only as a requester and never as an accepter.
A user may appear only as an accepter and never as a requester.
The user with the most friends might not appear frequently in one column alone, so counting only requester_id or only accepter_id would be incorrect.
There may be only one accepted request in the entire table.
In the follow-up scenario, multiple users could share the same maximum friend count.

Approaches

Brute-Force Approach

A brute-force solution would examine every user individually and count how many friendships involve that user.

One way to do this is:

Extract all distinct user IDs from both requester_id and accepter_id.
For each user, scan the entire table again and count how many rows contain that user in either column.
Keep track of the maximum count seen so far.

This approach is correct because every friendship involving the user contributes exactly one to their friend count. By checking all rows for every user, we eventually compute every user's degree accurately.

However, this approach is inefficient because the table is repeatedly scanned. If there are N friendship records and U unique users, the total work becomes O(U * N). In large datasets, this repeated scanning becomes unnecessarily expensive.

Optimal Approach

The key insight is that every accepted friendship contributes exactly one friend to both participants.

Instead of processing each user separately, we can process each friendship once and immediately increment the friend count for both users involved.

Conceptually, we can transform the table into a unified stream of user appearances:

(requester_id)
(accepter_id)

Then we group by user ID and count how many times each user appears.

In SQL, this is naturally expressed using UNION ALL:

One query extracts all requesters.
Another query extracts all accepters.
Combining them creates one row per friendship participation.
Grouping and counting gives the total number of friends for each user.

Finally, we sort by friend count descending and return the top user.

This solution processes every friendship only once, making it significantly more efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(U * N)	O(U)	Repeatedly scans the table for every user
Optimal	O(N)	O(U)	Counts all friendships in a single aggregation pass

Algorithm Walkthrough

Create a unified list of all friendship participations.

Every accepted friendship involves two users. We therefore create one combined dataset containing:

every requester_id
every accepter_id

We use UNION ALL instead of UNION because we want to preserve all occurrences. Each occurrence represents one friendship contribution. 2. Group the combined dataset by user ID.

After combining the two columns, each row represents one friendship participation by a user. Grouping by user ID allows us to count how many friendships each user has. 3. Count the number of rows for each user.

The count for a given user equals the total number of friends that user has. 4. Sort the users by friend count in descending order.

The user with the highest count should appear first. 5. Return the top result.

Since the problem guarantees only one user has the maximum number of friends, we can safely use LIMIT 1.

Why it works

Each accepted friendship contributes exactly one friend to both participants. By converting every friendship into two separate user appearances, one for the requester and one for the accepter, the total number of appearances for a user becomes exactly equal to their number of friends. Grouping and counting therefore computes the correct friend totals for every user.

Python Solution

# Write your MySQL query statement below

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

This solution begins by constructing a derived table named friendships.

The first query selects all requester_id values and renames the column to id. The second query selects all accepter_id values and also renames the column to id.

Using UNION ALL combines both result sets while preserving duplicates. Preserving duplicates is important because every occurrence represents a distinct friendship participation.

After constructing this combined dataset, the query groups by id. The COUNT(*) operation then computes how many times each user appears, which corresponds directly to the number of friends that user has.

Finally, the results are sorted in descending order by friend count, and LIMIT 1 returns the user with the maximum number of friends.

Go Solution

// Write your MySQL query statement below

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

Since this is a database problem on LeetCode, the solution is written entirely in SQL rather than Go application code. The same SQL query is submitted regardless of the language selected in the interface.

The logic remains identical:

Flatten both friendship columns into one stream of user IDs.
Count occurrences per user.
Return the user with the highest count.

Worked Examples

Example 1

Input 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

Step 1: Build unified friendship participation table

From requester_id:

id
1
1
2
3

From accepter_id:

id
2
3
3
4

Combined using UNION ALL:

id
1
1
2
3
2
3
3
4

Step 2: Group and count

id	count
1	2
2	2
3	3
4	1

Step 3: Sort descending

id	num
3	3
1	2
2	2
4	1

Step 4: Return top row

id	num
3	3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Each friendship row is processed a constant number of times
Space	O(U)	Aggregation stores counts for each unique user

The query scans the table twice, once for requesters and once for accepters, but both scans are linear in the number of rows. Grouping operations require storing counts for unique users, which gives O(U) auxiliary space where U is the number of distinct users.

Test Cases

# Example from the problem statement
# User 3 has the highest number of friends
assert solution([
    [1, 2],
    [1, 3],
    [2, 3],
    [3, 4]
]) == (3, 3)

# Single friendship
# Both users have one friend
assert solution([
    [1, 2]
]) in [(1, 1), (2, 1)]

# User appears only as requester
assert solution([
    [1, 2],
    [1, 3],
    [1, 4]
]) == (1, 3)

# User appears only as accepter
assert solution([
    [2, 1],
    [3, 1],
    [4, 1]
]) == (1, 3)

# Larger friendship network
assert solution([
    [1, 2],
    [2, 3],
    [2, 4],
    [2, 5],
    [3, 4]
]) == (2, 4)

# Tie scenario for follow-up discussion
# Users 1 and 2 both have two friends
assert set(solution_all([
    [1, 2],
    [1, 3],
    [2, 3]
])) == {(1, 2), (2, 2), (3, 2)}

# Sparse graph
assert solution([
    [10, 20],
    [30, 40]
]) in [(10, 1), (20, 1), (30, 1), (40, 1)]

Test	Why
Basic example	Verifies standard counting behavior
Single friendship	Tests smallest non-empty input
User only requester	Ensures requester counts are included
User only accepter	Ensures accepter counts are included
Larger network	Verifies aggregation correctness
Tie scenario	Tests follow-up case with multiple maxima
Sparse graph	Ensures disconnected friendships work correctly

Edge Cases

One important edge case occurs when a user appears only in the requester_id column and never in the accepter_id column. A flawed implementation that only counts accepters would incorrectly ignore this user's friendships. The solution avoids this problem by combining both columns using UNION ALL.

Another important edge case occurs when a user appears only as an accepter. This is symmetric to the previous case and similarly demonstrates why both columns must be processed equally. Because the query extracts IDs from both columns independently, the implementation handles this correctly.

A third important edge case involves ties. Although the original problem guarantees a unique maximum, real-world data often contains multiple users with the same number of friends. A naive LIMIT 1 solution would arbitrarily discard tied users. The follow-up version can be solved by computing the maximum friend count separately and returning all users whose count equals that maximum.

A final subtle edge case involves duplicate handling. Using UNION instead of UNION ALL would remove duplicate rows and produce incorrect friend counts because repeated appearances are meaningful. Each friendship participation must be counted independently, which is why UNION ALL is required.