Domain 2MediumCORE

Friend Requests II: Who Has the Most Friends

Restatement: We are given a dataset representing accepted friend requests between users. The goal is to identify which user has established friendships with the highest number of other distinct individuals and return that count along with their ID (or just the ID, depending on specific requirements; I'll assume returning both for clarity).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 1

602. Friend Requests II: Who Has the Most Friends

Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 57.9%


Problem Breakdown

Restatement: We are given a dataset representing accepted friend requests between users. The goal is to identify which user has established friendships with the highest number of other distinct individuals and return that count along with their ID (or just the ID, depending on specific requirements; I’ll assume returning both for clarity).

Schema Assumption: Based on standard LeetCode “Friend Requests” problems, we have a table RequestAccepted containing two columns:

  1. requester_id: The user who sent the request.
  2. acceptee_id: The user who accepted it (establishing a connection).

Inputs & Outputs:

  • Input: A list of tuples representing rows from RequestAccepted, e.g., (user_A, user_B).
  • Output: A tuple or dictionary containing the User ID and their friend count. If there are ties for the most friends, we typically return all such users (or one depending on strictness; I’ll handle returning a list of top candidates).

Constraints & Edge Cases:

  1. Empty Input: What if no requests exist? The result should reflect that or be handled gracefully (e.g., empty set).
  2. Duplicates: Can the same (requester, acceptee) pair appear twice? Usually not in a relational DB schema for this problem type, but robust code handles it by counting unique connections per user rather than raw row counts if possible. However, standard aggregation usually assumes distinct edges unless specified otherwise. I will assume we count valid connection instances provided in the input list.
  3. Ties: If multiple users have the same max friend count, should we return all? In SQL/DB contexts, often LIMIT or specific tie-breaking rules apply. For a Python solution, returning a sorted list of top candidates is safer and more complete than arbitrarily picking one.

Intuition

Starting Point (Brute Force): The most naive approach would be to iterate through every user in the dataset and for each user, scan all other rows to count how many times they appear as either requester_id or acceptee_id.

  • Complexity: If there are NN users and we check connections naively without aggregation, this could degrade towards O(N2)O(N^2) if not careful. Even simpler: iterating through the list of rows to count occurrences for each user is better (O(Rows)O(Rows)), but finding the max requires scanning all counts at the end anyway.
  • Why Insufficient: While linear scan seems okay, doing this without a data structure (like a hash map) makes it hard to manage state efficiently if we were processing streams or large datasets where memory locality matters. More importantly, in an interview context, simply saying “loop through and count” is often seen as lacking optimization awareness compared to using aggregation primitives like Counter or Hash Maps which are designed for frequency counting.

Key Insight: This problem maps directly to finding the node with the highest degree (number of edges) in a graph where rows represent undirected edges between two nodes (requester_id, acceptee_id). Since we just need counts, we don’t care about order or specific IDs until aggregation is done. We can use a Hash Map (Python Dictionary) to track how many times each user appears across both columns of the input data.

  • Optimization: By iterating through the rows once and updating counters in O(1)O(1) time per row, we achieve linear time complexity relative to the number of records (NN).

Approach

Algorithm Design:

  1. Initialize a dictionary (or collections.Counter) called friend_counts. Keys will be user IDs, values will be integer counts.
  2. Iterate through each record (requester_id, acceptee_id) in the input data:
    • Increment count for requester_id by 1.
    • Increment count for acceptee_id by 1.
  3. After processing all rows, find the maximum value in our dictionary and identify which user(s) correspond to it.
  4. Return the result (User ID + Count).

Why this works: This approach treats each row as an edge connecting two nodes. Since a friendship is established by acceptance of request, every valid entry represents one connection for both parties involved in that specific transaction. By aggregating occurrences per user across all rows, we get their total degree (friend count) efficiently.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of records in RequestAccepted. We iterate through each row exactly once to update counters (O(1)O(1) dictionary operations). Finding the max takes another pass over unique users, which is at most M≤NM \le N. Total time remains linear.
  • Space Complexity: O(M)O(M) where MM is the number of distinct user IDs in the dataset (keys in our hash map). In worst case, every row involves a new user (M=NM=N), so space scales with input size but typically much less than raw rows if users are reused.

Solution

from collections import Counter
from typing import List, Tuple, Optional

def get_most_friends(request_accepted: List[Tuple[int, int]]) -> Optional[List[dict]]:
    """
    Identifies the user(s) with the most friends based on accepted requests.
    
    Args:
        request_accepted: A list of tuples (requester_id, acceptee_id).
        
    Returns:
        A list of dictionaries containing 'user_id' and 'friend_count'. 
        If no data exists or only one user has connections, returns appropriate result.
    """
    if not request_accepted:
        return []

    # Use a Counter to aggregate occurrences for both requester and acceptee
    friend_counts = Counter()
    
    for requester_id, acceptee_id in request_accepted:
        # Each row represents an accepted connection between two users.
        # Both parties gain one "friend" count from this valid interaction.
        friend_counts[requester_id] += 1
        friend_counts[acceptee_id] += 1
    
    if not friend_counts:
        return []

    max_friends = max(friend_counts.values())
    
    # Collect all users who have the maximum number of friends to handle ties correctly.
    top_users = [
        {"user_id": uid, "friend_count": count} 
        for uid, count in friend_counts.items() if count == max_friends
    ]

    return sorted(top_users, key=lambda x: x['user_id']) # Optional sort by ID for determinism

# Example usage (uncomment to test locally)
if __name__ == "__main__":
    data = [(1, 2), (3, 4), (5, 6)] 
    print(get_most_friends(data))

Edge Cases Handled

  • Empty Input: The function checks if not request_accepted and returns an empty list immediately to avoid errors on max() or iteration.
  • Single User Connections: If only one user appears in the data, they will be returned with their count (1).
  • Ties for Most Friends: Instead of arbitrarily picking a single winner using max, we filter all users who match the maximum value and return them as a list. This is more robust than assuming unique winners without explicit tie-breaking rules provided in requirements.
  • Large Datasets: Using Counter (hash map) ensures O(1)O(1) lookups/updates, preventing performance degradation that might occur with nested loops or sorting large lists repeatedly during the counting phase.