602. Friend Requests II: Who Has the Most Friends - Solution

The problem

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?

Approach overview

Problem Overview: You are given a table of accepted friend requests where each row contains a requester and an accepter. Once a request is accepted, both users become friends. The task is to determine which user has the highest number of friends.

Approach 1: SQL Aggregation with UNION ALL (O(n) time, O(n) space)

The key observation is that every accepted request contributes one friend to both the requester and the accepter. In SQL, you can normalize the data by converting both columns into a single list of user IDs using UNION ALL. After that, perform a GROUP BY on the user ID and count how many times each appears. The user with the highest count has the most friends. Sorting the counts in descending order and returning the top record gives the answer. This approach relies on SQL aggregation and works efficiently because it scans the table only once.

Approach 2: HashMap Friend Counter (O(n) time, O(n) space)

If you solve the same problem outside SQL (for example in Python or C++), use a dictionary or hash map to count friendships. Iterate through every accepted request. For each pair (requester_id, accepter_id), increment the count for both users in the map. This effectively treats each row as two friendship edges. After processing all rows, iterate through the map to find the user with the maximum count. Hash lookups and updates are constant time, which keeps the overall complexity linear. This method uses a classic hash map frequency counting pattern and is straightforward to implement in most languages.

Both approaches rely on the same idea: an accepted request increases the friend count of two users. The difference is mainly the execution environment. SQL leverages grouping and aggregation directly in the database, while application-level solutions simulate the same behavior using in-memory structures.

Recommended for interviews: Interviewers typically expect the counting insight first: every row contributes two friendships. From there, the optimal implementation is either a SQL aggregation query using database grouping or a hash map counter in code. Demonstrating the brute counting logic quickly shows understanding of the data model, while the optimized linear solution shows comfort with aggregation and hash-based counting.

Approach 1: SQL Aggregation and Joined Count

The main idea here is to see every occurrence of an ID as a friendship connection, whether it appears as a requester or an accepter. We'll thus aggregate the ID counts to find out who has the maximum number of occurrences, meaning the maximum number of friends.

First, we can treat requesters and accepters separately and count how many times a person appears as a requester or an accepter, then sum these counts to get the total number of friends for each ID. Finally, we can select the ID with the maximum sum of appearances.

MySQL

SELECT id, num FROM ( SELECT id, COUNT(id) as num FROM ( SELECT requester_id as id FROM RequestAccepted UNION ALL SELECT accepter_id as id FROM RequestAccepted ) as friends GROUP BY id ) as counts ORDER BY num DESC LIMIT 1;

We first create a subquery to combine all requesters and accepters into a single list using UNION ALL. We then count the occurrences of each individual in this list, which represents the number of friendships they have. Finally, we sort these counts in descending order and select the top result.

Complexity

Time Complexity: O(n log n) due to sorting operation. Space Complexity: O(n) for storing the consolidated list of all IDs.

Try this approach in the editor

Approach 2: Use of Dictionary (HashMap) to Count Friends

This approach can be employed in programming languages such as Python, Java, and C# where dictionaries (or hashmaps) are effective for counting occurrences.

For each row in the data, increment the friendship count for both the requester and the accepter in a dictionary (or hashmap). After processing, iterate through the dictionary to find the ID with the maximum count.

Python

def find_most_friends(requests):
    from collections import defaultdict
    friend_count = defaultdict(int)
    for request in requests:
        requester, accepter = request
        friend_count[requester] += 1
        friend_count[accepter] += 1
    max_friends = max(friend_count.values())
    for person, count in friend_count.items():
        if count == max_friends:
            return person, count
requests = [(1, 2), (1, 3), (2, 3), (3, 4)]
print(find_most_friends(requests))  # Output: (3, 3)

C++

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
pair<int, int> find_most_friends(vector<pair<int, int>>& requests) {
    unordered_map<int, int> friend_count;
    for (auto& request : requests) {
        friend_count[request.first]++;
        friend_count[request.second]++;
    }
    int max_friends = 0;
    int person_id = -1;
    for (auto& entry : friend_count) {
        if (entry.second > max_friends) {
            max_friends = entry.second;
            person_id = entry.first;
        }
    }
    return {person_id, max_friends};
}
int main() {
    vector<pair<int, int>> requests = {{1, 2}, {1, 3}, {2, 3}, {3, 4}};
    auto result = find_most_friends(requests);
    cout << "ID: " << result.first << ", Number of Friends: " << result.second << endl;
    return 0;
}

Using the Python defaultdict, we initialize counts to zero and update them by iterating over each friendship in the list. After updating, we calculate the maximum count and figure out which person has this maximum count.

Complexity

Time Complexity: O(n) since we pass through the data once and dictionary operations are generally O(1). Space Complexity: O(n) for storing the friend counts.

Try this approach in the editor

Complexity comparison

Approach	Complexity
SQL Aggregation and Joined Count	Time Complexity: `O(n log n)` due to sorting operation. Space Complexity: `O(n)` for storing the consolidated list of all IDs.
Use of Dictionary (HashMap) to Count Friends	Time Complexity: `O(n)` since we pass through the data once and dictionary operations are generally O(1). Space Complexity: `O(n)` for storing the friend counts.

Complexity analysis

Approach	Time	Space	When to Use
SQL Aggregation with UNION ALL	O(n)	O(n)	Best when solving directly in a database environment using SQL queries
HashMap Friend Counter	O(n)	O(n)	General programming solution in languages like Python or C++

Frequently asked questions

Is Friend Requests II: Who Has the Most Friends easy or hard?

The problem is rated Medium because the logic is simple but requires recognizing that each accepted request contributes to two users' friend counts. Once that insight is clear, the implementation with SQL aggregation or a hash map becomes straightforward.

Friend Requests II: Who Has the Most Friends Python/Java solution

In Python, iterate through the request pairs and update a dictionary counter for both users, then return the user with the maximum count. In Java, the same logic is implemented with a HashMap<Integer, Integer>. Both versions run in O(n) time and O(n) space.

How to solve Friend Requests II: Who Has the Most Friends in O(n)?

Process each accepted request exactly once and update the friend count for both the requester and the accepter. In SQL, use UNION ALL followed by GROUP BY to count occurrences. In Python or C++, maintain a hash map where each user ID maps to their friend count.

What is the best approach for Friend Requests II: Who Has the Most Friends?

The optimal approach counts how many times each user appears in accepted friend requests. In SQL, use UNION ALL to combine requester_id and accepter_id into a single column, then GROUP BY and count. In code, iterate through the requests and increment counts in a hash map for both users. Both solutions run in O(n) time.

Is Friend Requests II: Who Has the Most Friends asked at Google/Amazon/Meta?

Database aggregation and counting problems like this frequently appear in SQL interviews at companies such as Meta, Amazon, and other data-focused roles. The question tests understanding of grouping, aggregation, and relationship modeling in relational tables.

What data structure is used in Friend Requests II: Who Has the Most Friends?

The main data structure is a hash map (dictionary) that stores user IDs as keys and their friend counts as values. In SQL solutions, the equivalent concept is implemented through GROUP BY aggregation on a combined column of user IDs.

What is the time complexity of Friend Requests II: Who Has the Most Friends?

The optimal solution runs in O(n) time where n is the number of accepted requests. Each row is processed once, either during SQL aggregation or while updating counts in a hash map. Space complexity is O(n) to store friend counts for users.

Friend Requests II: Who Has the Most Friends solution and explanation

The problem

Approach overview

Approach 1: SQL Aggregation and Joined Count

Approach 2: Use of Dictionary (HashMap) to Count Friends

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Friend Requests II: Who Has the Most Friends solution and explanation

The problem

Approach overview

Approach 1: SQL Aggregation and Joined Count

Approach 2: Use of Dictionary (HashMap) to Count Friends

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems