{x}
blog image

Find Followers Count

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}

Solution Explanation:

The problem asks to find the number of followers for each user in the Followers table. The solution uses a SQL query to achieve this.

Approach:

The core idea is to group the data by user_id and then count the occurrences of each user_id within each group. This count represents the number of followers for that specific user. The COUNT() aggregate function is used to perform the counting, and GROUP BY clause groups the rows based on the user_id. Finally, the results are ordered by user_id in ascending order using ORDER BY.

MySQL Code:

SELECT user_id, COUNT(1) AS followers_count
FROM Followers
GROUP BY 1
ORDER BY 1;

  • SELECT user_id, COUNT(1) AS followers_count: This selects the user_id and the count of rows for each user_id. COUNT(1) counts all rows in each group. AS followers_count gives the resulting count column a more descriptive name.

  • FROM Followers: This specifies the table from which to retrieve the data.

  • GROUP BY 1: This groups the rows based on the first column in the SELECT statement, which is user_id. Using 1 as shorthand is a common SQL practice to refer to the first column in the SELECT list.

  • ORDER BY 1: This sorts the final result set in ascending order based on the first column in the SELECT statement (user_id).

Time Complexity Analysis:

The time complexity of this SQL query depends on the database system's implementation of GROUP BY and ORDER BY. In general, a well-optimized database system will use efficient indexing and algorithms to achieve a time complexity close to O(N log N) or even O(N) in favorable cases (where N is the number of rows in the Followers table), especially if an index exists on the user_id column. In the worst-case scenario (no index and poor database optimization), it could be O(N^2). However, in practical scenarios with a reasonable number of rows and efficient indexing, the query should be very efficient.

Space Complexity Analysis:

The space complexity depends on the size of the output, which is the number of unique user_id values. In the worst-case scenario, where every row has a unique user_id, the space complexity would be O(N), where N is the number of rows in the Followers table. In practice, the space complexity is typically less than O(N) because the number of unique users is often significantly smaller than the total number of rows (due to multiple followers per user).