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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5
using namespace std;
vector<pair<int, int>> findFollowersCount(vector<pair<int, int>>& followers) {
unordered_map<int, int> followersCount;
for (const auto& p : followers) {
followersCount[p.first]++;
}
vector<pair<int, int>> result;
for (const auto& entry : followersCount) {
result.push_back(entry);
}
sort(result.begin(), result.end());
return result;
}
// Example usage
int main() {
vector<pair<int, int>> followers = { {0, 1}, {1, 0}, {2, 0}, {2, 1} };
auto result = findFollowersCount(followers);
for (const auto& p : result) {
cout << "User ID: " << p.first << ", Followers Count: " << p.second << endl;
}
return 0;
}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.