Skip to main content
Talentd

Friend Requests II: Who Has the Most Friends - Solution & Explanation

MediumDatabase6 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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.

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.

Code

SQL

SQL

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.

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.

Code

PythonC++

Python

C++

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 →

Approach 3: Union All + Group By

We can merge the requester_id and accepter_id columns into a single column, representing each person's friend relationships. Then we group the merged result and count, finding the person with the most friends and the number of friends.

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.

Union All + Group By—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
SQL Aggregation with UNION ALLO(n)O(n)Best when solving directly in a database environment using SQL queries
HashMap Friend CounterO(n)O(n)General programming solution in languages like Python or C++

Video Solution

Friend Requests II: Who Has the Most Friends | Leetcode 602 | Crack SQL Interviews in 50 Qs #mysql • Learn With Chirag • 8,482 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Friend Requests II: Who Has the Most Friends with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary