Find Followers Count - Solution & Explanation
Problem Statement
Table: Followers
+-------------+------+ | Column Name | Type | +-------------+------+ | user_id | int | | follower_id | int | +-------------+------+ (user_id, follower_id) is the primary key (combination of columns with unique values) for this table. This table contains the IDs of a user and a follower in a social media app where the follower follows the user.
Write a solution that will, for each user, return the number of followers.
Return the result table ordered by user_id in ascending order.
The result format is in the following example.
Example 1:
Input:
Followers table:
+---------+-------------+
| user_id | follower_id |
+---------+-------------+
| 0 | 1 |
| 1 | 0 |
| 2 | 0 |
| 2 | 1 |
+---------+-------------+
Output:
+---------+----------------+
| user_id | followers_count|
+---------+----------------+
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
+---------+----------------+
Explanation:
The followers of 0 are {1}
The followers of 1 are {0}
The followers of 2 are {0,1}
Approach Overview
Problem Overview: You are given a Followers table where each row represents a follower relationship: (user_id, follower_id). The task is to compute how many followers each user has and return the results sorted by user_id.
Approach 1: SQL-like Aggregation (O(n) time, O(k) space)
The most direct way to solve this database-style problem is grouping records by user_id and counting how many rows belong to each group. In SQL this is done with GROUP BY and COUNT(*). When implemented in languages like Python or JavaScript, you simulate this behavior by grouping rows by key and incrementing a counter. The key insight is that every row contributes exactly one follower to the corresponding user_id. This approach scans the dataset once and maintains a running count per user.
Conceptually this mirrors database aggregation operations covered in database problems. The grouping step ensures each user appears once in the result set with their follower total.
Approach 2: Hash Map / Dictionary Counting (O(n) time, O(k) space)
Another way to think about the same operation is explicit frequency counting using a hash map. Iterate through every row in the table and store counts in a dictionary where the key is user_id and the value is the follower count. Each iteration performs a constant-time hash lookup and increments the stored value. After processing all rows, sort the keys and output the results.
This approach relies on a hash table to maintain counts efficiently. It mirrors how many database engines internally implement aggregation operations. Because each relationship is processed once, the runtime remains linear in the number of rows.
Recommended for interviews: The aggregation idea is the expected solution since the problem is fundamentally a grouping query. Explaining the SQL GROUP BY version shows you understand relational operations. Implementing the same logic with a hash map demonstrates algorithmic thinking and gives an optimal O(n) time solution with O(k) space, where k is the number of unique users.
Approach 1: Use SQL-like Aggregation
This approach involves using an SQL-like query to count the number of followers for each user by grouping the records by user_id. This can be achieved using a GROUP BY clause and the COUNT function.
This Python solution uses a defaultdict to count the followers for each user. We iterate over the input list of tuples, updating the count of followers for each user_id. Finally, we return the result sorted by user_id.
Code
Python
JavaScript
Complexity
Time Complexity: O(n), where n is the number of records in the table because each record is processed once.
Space Complexity: O(u), where u is the number of distinct user_ids because we're storing results for each user.
Approach 2: Use Hash Maps or Dictionaries
This approach relies on using hash maps or dictionaries to keep track of the follower counts for each user. It directly translates the SQL GROUP BY method into a coding solution using dictionary data structures available in multiple languages.
This C++ solution utilizes an unordered_map to count followers for each user_id. It iterates over the input vector, updating the map. Finally, it extracts the counts into a vector of pairs and sorts it, mimicking a GROUP BY query in SQL.
Complexity
Time Complexity: O(n log u), where n is the number of records and u is the number of unique user_ids, because of the sort operation.
Space Complexity: O(u) for storing follower counts.
Approach 3: Grouping and Aggregation
We can directly group the Followers table by user_id, and use the COUNT function to count the number of followers for each user.
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| Use SQL-like Aggregation | Time Complexity: O(n), where n is the number of records in the table because each record is processed once. |
| Use Hash Maps or Dictionaries | Time Complexity: O(n log u), where n is the number of records and u is the number of unique |
| Grouping and Aggregation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL Aggregation (GROUP BY) | O(n) | O(k) | Best for database queries or SQL-style problems where grouping and counting rows is required |
| Hash Map / Dictionary Counting | O(n) | O(k) | Useful when implementing the logic in general-purpose languages like C++, C#, Python, or JavaScript |
Video Solution
Find Followers Count | Leetcode 1729 | Crack SQL Interviews in 50 Qs #mysql #leetcode • Learn With Chirag • 4,805 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Followers Count easy or hard?
Find Followers Count Python/Java solution
How to solve Find Followers Count in O(n)?
What is the best approach for Find Followers Count?
Is Find Followers Count asked at Google/Amazon/Meta?
What data structure is used in Find Followers Count?
What is the time complexity of Find Followers Count?
Ready to solve this problem?
Practice Find Followers Count with our built-in code editor and test cases.
Practice on FleetCode