Sponsored
Sponsored
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.
Time Complexity: O(n log n) due to sorting operation. Space Complexity: O(n) for storing the consolidated list of all IDs.
1SELECT 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.
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.
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.
1def find_most_friends(requests):
2Using 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.