1729. Find Followers Count Solution

The problem

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.

Python

from collections import defaultdict

def find_followers_count(followers):
    followers_count = defaultdict(int)
    for user_id, follower_id in followers:
        followers_count[user_id] += 1

    return sorted([(user_id, count) for user_id, count in followers_count.items()])

# Example usage
followers = [(0, 1), (1, 0), (2, 0), (2, 1)]
print(find_followers_count(followers))

JavaScript

function findFollowersCount(followers) {
    const followersCount = {};

    followers.forEach(([userId, followerId]) => {
        if (!followersCount[userId]) {
            followersCount[userId] = 0;
        }
        followersCount[userId]++;
    });

    return Object.entries(followersCount)
        .map(([userId, count]) => ({ user_id: Number(userId), followers_count: count }))
        .sort((a, b) => a.user_id - b.user_id);
}

// Example usage
const followers = [ [0, 1], [1, 0], [2, 0], [2, 1] ];
console.log(findFollowersCount(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.

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.

Try this approach in the editor

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.

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

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;
}

using System;
using System.Collections.Generic;
using System.Linq;

class 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}"));
    }
}

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.

Try this approach in the editor

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.

MySQL

# Write your MySQL query statement below
SELECT user_id, COUNT(1) AS followers_count
FROM Followers
GROUP BY 1
ORDER BY 1;

Try this approach in the editor

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. Space Complexity: O(u), where u is the number of distinct `user_id`s because we're storing results for each user.
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 `user_id`s, because of the sort operation. Space Complexity: O(u) for storing follower counts.
Grouping and Aggregation	–

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

Frequently asked questions

Is Find Followers Count easy or hard?

Find Followers Count is considered an Easy database problem. The main idea is recognizing that each row contributes one follower and grouping rows by user_id. Once you apply aggregation or hash map counting, the implementation becomes straightforward.

Find Followers Count Python/Java solution

In Python, use a dictionary or collections.Counter to accumulate counts per user_id while iterating through the rows. In Java or similar languages, use a HashMap<Integer, Integer> and increment the count for each user. The logic mirrors SQL aggregation and runs in O(n) time.

How to solve Find Followers Count in O(n)?

Iterate through all rows in the Followers table and maintain a dictionary keyed by user_id. For every row, increment the follower count for that user. After processing all rows, sort the user IDs and output their counts. Each row is visited once, giving O(n) time complexity.

What is the best approach for Find Followers Count?

The best approach is aggregation by user_id. In SQL this uses GROUP BY with COUNT(*). In general programming languages, the same logic is implemented using a hash map that counts how many times each user_id appears. Both methods run in O(n) time where n is the number of rows in the Followers table.

Is Find Followers Count asked at Google/Amazon/Meta?

Problems involving aggregation and counting relationships appear frequently in database and data-processing interviews at companies like Amazon, Meta, and Google. While the exact problem may vary, the core concept of grouping records and computing counts is commonly tested.

What data structure is used in Find Followers Count?

The typical data structure is a hash map (dictionary) that stores user_id as the key and the number of followers as the value. In SQL-based solutions, the database engine performs the equivalent operation using GROUP BY aggregation internally.

What is the time complexity of Find Followers Count?

The optimal solution runs in O(n) time because each follower relationship is processed exactly once. A hash map or database aggregation keeps track of counts while iterating through the rows. The space complexity is O(k), where k is the number of distinct users.

Find Followers Count solution and explanation

The problem

Approach overview

Approach 1: Use SQL-like Aggregation

Approach 2: Use Hash Maps or Dictionaries

Approach 3: Grouping and Aggregation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Followers Count solution and explanation

The problem

Approach overview

Approach 1: Use SQL-like Aggregation

Approach 2: Use Hash Maps or Dictionaries

Approach 3: Grouping and Aggregation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems