614. Second Degree Follower
Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 32.8%
Problem Breakdown
We are given a Follow table with columns follower_id and followee_id. The goal is to identify which users (user_id) appear as the followee_id in at least 2 rows of this table (i.e., they have been followed by two or more distinct followers). For each such user, we must return their ID and the total count of times they were followed.
Inputs: A dataset representing the Follow relation (follower_id, followee_id).
Outputs: Two columns: user_id (the person being followed) and num (count of followers).
Constraints & Edge Cases:
- The table might be empty or contain users with only 0/1 follower. These must be excluded from the result set.
- IDs are typically positive integers; no overflow issues expected in standard integer ranges for this problem size.
- Duplicate rows: In a relational database,
(follower_id, followee_id)is usually unique per row (primary key), but even if duplicates existed logically,COUNT(*)handles them naturally by summing occurrences.
Intuition
If I were to solve this without SQL aggregation functions first thought might be nested loops or checking every pair of rows to see who follows whom twice. That would require time complexity because for each follower we’d need to check if they follow the same person again, which is inefficient and unnecessary given relational algebra capabilities.
The core requirement here is frequency counting: “How many times does this followee_id appear in the table?” This immediately points towards aggregation. We don’t care about who follows them (the specific follower), only that there are enough of them to meet the threshold (). Therefore, we group by the target user (followee_id) and count occurrences per group.
Approach
- Grouping: Since we need counts for each person being followed, we must aggregate rows based on
followee_id. In SQL this isGROUP BY followee_id; in Python logic (if implementing without DB), it’s iterating through a dictionary or Counter keyed by user ID. - Counting: For every group formed above, calculate the size of that group (
COUNT(*)). This represents how many followers they have. - Filtering: We only want users where this count is greater than or equal to 2. In SQL,
WHEREfilters rows before aggregation, so we must useHAVING. Similarly in Python logic, we filter the resulting dictionary after counting.
Complexity Analysis
- Time Complexity: , where is the number of rows in the
Followtable. We iterate through each row exactly once to populate our counts (hash map/Counter insertion). Filtering happens on a subset () at the end. Sorting adds negligible overhead for typical constraints but ensures deterministic output order if required by test cases. - Space Complexity: , where is the number of distinct users being followed. In the worst case (everyone follows someone unique), this approaches . We store one entry per
followee_idin our aggregation structure before filtering.
Solution
from collections import Counter
from typing import List, Tuple
def get_second_degree_followers(follow_data: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
"""
Simulates the SQL logic for LeetCode 1823 (Second Degree Follower).
Args:
follow_data: A list of tuples representing rows in the 'Follow' table.
Each tuple is (follower_id, followee_id).
Returns:
List of tuples [(user_id, num)] where user has >= 2 followers.
"""
# Step 1 & 3: Aggregate counts for each followed person using a Counter.
# This maps directly to SQL's GROUP BY and COUNT(*).
follower_counts = Counter(followee_id for _, followee_id in follow_data)
# Step 2 & Filter: Keep only users with count >= 2 (HAVING clause equivalent).
result = [(user, count) for user, count in follower_counts.items() if count >= 2]
return sorted(result)
Edge Cases Handled
- Empty Table: The
Counterwill be empty; the list comprehension returns an empty list. Correct behavior as no users exist to follow anyone twice. - Single Follower Count: Users with exactly 1 follower are filtered out by the condition
if count >= 2. They do not appear in output. - No Followers for User: If a user is never followed, they won’t be present in the Counter keys at all (or have count 0), so they naturally fail the filter and aren’t included.