Friend Requests II: Who Has the Most Friends - Video Solutions

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.