LeetCode 602: Friend Requests II: Who Has the Most Friends Solution in Python – A Step-by-Step Guide
Imagine you’re managing a social network, tracking who’s sending and receiving friend requests, and you need to crown the most popular person—the one with the most connections, counting both requests they’ve sent and received. That’s the gist of LeetCode 602: Friend Requests II: Who Has the Most Friends, a medium-level problem that’s all about tallying social ties from a request log. Using Python, we’ll explore two solutions: the Best Solution, a dictionary-based counting method that mimics SQL aggregation for speed, and an Alternative Solution, a graph-based approach with an adjacency list that’s more visual but less efficient. With detailed examples, beginner-friendly breakdowns—especially for the dictionary method—and clean code, this guide will help you find the social star, whether you’re new to coding or leveling up. Let’s dive into the friend network and start counting!
What Is LeetCode 602: Friend Requests II: Who Has the Most Friends?
In LeetCode 602: Friend Requests II: Who Has the Most Friends, you’re given a table request_accepted with columns requester_id, accepter_id, and accept_date, representing accepted friend requests. Your task is to find the person (by ID) with the most friends—where “friends” means the total number of requests they’ve sent (as requester) or received (as accepter)—and return their ID and friend count. For example, if ID 1 sends requests to 2 and 3, and receives one from 4, they have 3 friends. This problem tests your ability to aggregate data, often posed as an SQL query, but we’ll tackle it in Python for a coding spin.
Problem Statement
- Input: A list of records (or table rows) with [requester_id, accepter_id, accept_date].
- Output: A list [id, num] where id is the person with the most friends, and num is their friend count.
- Rules:
- Count each unique requester-accepter pair once.
- A person’s friend count is the sum of requests sent and received.
Constraints
- Table has at least 1 row.
- requester_id and accepter_id are positive integers, distinct in each row.
- Multiple requests between the same pair are possible but count as one friendship.
Examples
- Input: ``` requester_id | accepter_id | accept_date 1 | 2 | 2025-01-01 1 | 3 | 2025-01-02 2 | 3 | 2025-01-03 ```
- Output: [1, 2] (ID 1 has 2 friends: 2 and 3)
- Input: ``` requester_id | accepter_id | accept_date 1 | 2 | 2025-01-01 1 | 3 | 2025-01-02 2 | 1 | 2025-01-03 3 | 1 | 2025-01-04 ```
- Output: [1, 4] (ID 1 has 4 friends: sent to 2, 3; received from 2, 3)
These examples show how friendships stack up—let’s solve it!
Understanding the Problem: Counting Friends
To solve LeetCode 602: Friend Requests II: Who Has the Most Friends in Python, we need to process a list of request records and count each person’s total friends—requests sent plus requests received—then find the maximum. A naive approach might loop through records multiple times, but that’s overkill. Instead, we’ll use:
- Best Solution (Dictionary Counting): O(n) time, O(n) space—fast and straightforward.
- Alternative Solution (Graph with Adjacency List): O(n) time, O(n) space—visual but more complex.
Let’s start with the dictionary solution, breaking it down for beginners.
Best Solution: Dictionary Counting with SQL-Like Logic
Why This Is the Best Solution
The dictionary counting approach is the top pick for LeetCode 602 because it’s efficient—O(n) time and O(n) space—and mimics SQL’s GROUP BY and COUNT in a Python-friendly way. It tallies each person’s sent and received requests in one pass, using a dictionary to track counts, then finds the max. It’s like keeping a quick scorecard of everyone’s social activity!
How It Works
Think of this as tallying friends on a leaderboard:
- Step 1: Initialize a Counter:
- Use a dictionary to track each ID’s friend count.
- Step 2: Process Requests:
- For each record [req_id, acc_id, date]:
- Increment req_id’s count (sent a request).
- Increment acc_id’s count (received a request).
- Step 3: Find the Max:
- Scan the dictionary for the ID with the highest count.
- Step 4: Return Result:
- Return [id, count] for the winner.
It’s like counting handshake partners—quick and simple!
Step-by-Step Example
Example:
requester_id | accepter_id | accept_date
1 | 2 | 2025-01-01
1 | 3 | 2025-01-02
2 | 3 | 2025-01-03- Initialize: count = {}.
- Record 1 (1, 2):
- count[1] = 1 (sent to 2).
- count[2] = 1 (received from 1).
- Record 2 (1, 3):
- count[1] = 2 (sent to 3).
- count[3] = 1 (received from 1).
- Record 3 (2, 3):
- count[2] = 2 (sent to 3).
- count[3] = 2 (received from 2).
- Final Counts:
- ID 1: 2 friends.
- ID 2: 2 friends.
- ID 3: 2 friends.
- Max: ID 1 (or any tied ID), [1, 2].
Code with Detailed Line-by-Line Explanation
Here’s the Python code, explained clearly:
from collections import defaultdict
class Solution:
def mostFriends(self, requests: List[List[int]]) -> List[int]:
# Step 1: Initialize dictionary for friend counts
count = defaultdict(int)
# Step 2: Count friends for each request
for req_id, acc_id, _ in requests:
count[req_id] += 1 # Sent a request
count[acc_id] += 1 # Received a request
# Step 3: Find the person with max friends
max_friends = 0
max_id = 0
for person_id, friend_count in count.items():
if friend_count > max_friends:
max_friends = friend_count
max_id = person_id
# Step 4: Return result
return [max_id, max_friends]- Line 1: Import defaultdict for convenience (defaults to 0).
- Line 6: Initialize count to track friends.
- Lines 9-11: Process each request:
- Increment req_id for sending.
- Increment acc_id for receiving.
- Lines 14-18: Find max:
- Compare each count, update max if higher.
- Line 21: Return [id, count].
- Time Complexity: O(n)—single pass through requests.
- Space Complexity: O(n)—dictionary size.
This is like a social tally—fast and neat!
Alternative Solution: Graph with Adjacency List
Why an Alternative Approach?
The graph-based approach builds an adjacency list to represent friendships—O(n) time, O(n) space. It’s more visual, treating requests as edges in an undirected graph, but it’s overkill for this problem since we don’t need the full structure. It’s like mapping a friend network to see who’s most connected.
How It Works
Picture this as drawing a friend web:
- Step 1: Build an undirected graph with an adjacency list.
- Step 2: For each request, add edges both ways (req_id ↔ acc_id).
- Step 3: Count each node’s degree (unique friends).
- Step 4: Find the node with the highest degree.
It’s like sketching connections and counting links!
Step-by-Step Example
Example:
requester_id | accepter_id | accept_date
1 | 2 | 2025-01-01
1 | 3 | 2025-01-02
2 | 3 | 2025-01-03- Graph:
- 1: [2, 3]
- 2: [1, 3]
- 3: [1, 2]
- Counts:
- ID 1: 2 friends.
- ID 2: 2 friends.
- ID 3: 2 friends.
- Max: ID 1, [1, 2].
Code for Graph Approach
from collections import defaultdict
class Solution:
def mostFriends(self, requests: List[List[int]]) -> List[int]:
# Step 1: Build adjacency list
graph = defaultdict(set)
for req_id, acc_id, _ in requests:
graph[req_id].add(acc_id) # Sent request
graph[acc_id].add(req_id) # Received request
# Step 2: Count friends and find max
max_friends = 0
max_id = 0
for person_id, friends in graph.items():
friend_count = len(friends)
if friend_count > max_friends:
max_friends = friend_count
max_id = person_id
return [max_id, max_friends]- Lines 6-9: Build graph with sets to avoid duplicates.
- Lines 12-17: Count unique friends per ID, find max.
- Time Complexity: O(n)—processing requests and counting.
- Space Complexity: O(n)—graph storage.
It’s a connected view of friendships!
Comparing the Two Solutions
- Dictionary Counting (Best):
- Pros: O(n) time, O(n) space, simple and fast.
- Cons: Less visual.
- Graph (Alternative):
- Pros: O(n) time, O(n) space, intuitive network view.
- Cons: Unnecessary complexity.
Dictionary wins for simplicity and speed.
Additional Examples and Edge Cases
- Input: [[1,2,"2025-01-01"]]
- Output: [1, 1] or [2, 1] (tie, any is fine).
- Input: [[1,2,"2025-01-01"], [2,1,"2025-01-02"]]
- Output: [1, 1] (same friendship, counted once).
Both handle these well.
Complexity Breakdown
- Dictionary: Time O(n), Space O(n).
- Graph: Time O(n), Space O(n).
Dictionary is optimal.
Key Takeaways
- Dictionary: Quick counting—smart!
- Graph: Visual connections—cool!
- Aggregation: Summing data is fun.
- Python Tip: Dictionaries rock—see Python Basics.