Sponsored
Sponsored
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.
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.
1from collections import defaultdict
2
3def find_followers_count(followers):
4 followers_count = defaultdict(int)
5 for user_id, follower_id in followers:
6 followers_count[user_id] += 1
7
8 return sorted([(user_id, count) for user_id, count in followers_count.items()])
9
10# Example usage
11followers = [(0, 1), (1, 0), (2, 0), (2, 1)]
12print(find_followers_count(followers))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.
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.
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.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Program {
public static List<(int userId, int followerCount)> FindFollowersCount(List<(int userId, int followerId)> followers) {
var followersCount = new Dictionary<int, int>();
foreach (var (userId, _) in followers) {
if (!followersCount.ContainsKey(userId)) {
followersCount[userId] = 0;
}
followersCount[userId]++;
}
return followersCount.Select(kvp => (kvp.Key, kvp.Value)).OrderBy(x => x.userId).ToList();
}
static void Main() {
var followers = new List<(int, int)> { (0, 1), (1, 0), (2, 0), (2, 1) };
var result = FindFollowersCount(followers);
result.ForEach(r => Console.WriteLine($"User ID: {r.userId}, Followers Count: {r.followerCount}"));
}
}The C# solution uses a Dictionary to track the number of followers for each user_id. It updates counts while iterating over the list of tuples. The results are then sorted and returned as a list in the required format.