LeetCode 1729 - Find Followers Count

LeetCode Problem 1729

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem is asking us to determine, for each user in a social media application, how many followers they have. The input is a table called Followers with two columns: user_id and follower_id. Each row represents a relationship where follower_id follows user_id. The combination (user_id, follower_id) is unique, so there are no duplicate follower entries for a user.

The expected output is a table containing each user_id along with the number of followers they have, labeled as followers_count. The results must be sorted by user_id in ascending order.

The constraints imply that the Followers table may contain multiple users and multiple followers per user, but every pair is unique. Edge cases include users with zero followers, a single user, or a single follower. The problem guarantees that user_id and follower_id are integers and the primary key ensures no duplicates.

Approaches

A brute-force approach would iterate over each user and count how many times that user appears as user_id in the table. While correct, this approach is inefficient because it may require scanning the entire table for every user, resulting in a high time complexity if the table is large.

The key insight for an optimal solution is to leverage SQL aggregation functions. By grouping the table by user_id and counting the rows for each group, we can calculate the number of followers directly and efficiently. Using GROUP BY ensures we process each user_id only once and ordering the result ensures it meets the output specification.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(u)	Count followers by scanning the table for each user; n is number of users, m is number of rows, u is distinct users
Optimal	O(m)	O(u)	Use SQL GROUP BY with COUNT(*); m is number of rows, u is distinct users

Algorithm Walkthrough

1. Identify all distinct user_id values in the Followers table.
2. Group all rows by user_id. This step ensures all followers for a specific user are collected together.
3. Count the number of rows in each group. This count represents the number of followers for that user_id.
4. Construct the output table with columns user_id and followers_count, using the counts obtained.
5. Order the results by user_id in ascending order. This is necessary to satisfy the output specification.

Why it works: Each row in the Followers table corresponds to exactly one follower relationship. Grouping by user_id and counting the rows in each group directly yields the number of followers per user. Ordering ensures the results are presented as requested.

Python Solution

import sqlite3
from typing import List, Tuple

def find_followers_count(cursor: sqlite3.Cursor) -> List[Tuple[int, int]]:
    query = """
    SELECT user_id, COUNT(*) AS followers_count
    FROM Followers
    GROUP BY user_id
    ORDER BY user_id ASC
    """
    cursor.execute(query)
    return cursor.fetchall()

In this implementation, the SQL query selects user_id and counts the number of followers for each user using COUNT(*). GROUP BY user_id groups the rows by user, and ORDER BY user_id ASC sorts the results. cursor.fetchall() returns the final list of tuples.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
)

func FindFollowersCount(db *sql.DB) ([][2]int, error) {
    query := `
    SELECT user_id, COUNT(*) AS followers_count
    FROM Followers
    GROUP BY user_id
    ORDER BY user_id ASC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results [][2]int
    for rows.Next() {
        var userID int
        var count int
        err := rows.Scan(&userID, &count)
        if err != nil {
            return nil, err
        }
        results = append(results, [2]int{userID, count})
    }
    return results, nil
}

In Go, we use db.Query to execute the SQL. We iterate over rows and scan the results into integer variables. We append each [2]int slice to the results. Go requires explicit error handling and closing of rows, which is handled with defer.

Worked Examples

For the given example:

Followers table:
| user_id | follower_id |
| 0       | 1           |
| 1       | 0           |
| 2       | 0           |
| 2       | 1           |

Step by step:

1. Group by user_id:

• 0 → [1] (count 1)
• 1 → [0] (count 1)
• 2 → [0, 1] (count 2)

2. Build the result table:

| user_id | followers_count |
| 0       | 1               |
| 1       | 1               |
| 2       | 2               |

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m)	Each row in the table is processed once in the GROUP BY operation, where m is the number of rows.
Space	O(u)	One entry per distinct user is stored for the aggregation, where u is the number of users.

The reasoning: SQL aggregation functions are optimized to scan each row once while maintaining an internal count per group. This results in linear time with respect to the table size and linear space relative to the number of unique users.

Test Cases

# Test cases
import sqlite3

conn = sqlite3.connect(":memory:")
c = conn.cursor()
c.execute("CREATE TABLE Followers (user_id INT, follower_id INT)")

# Example 1
c.executemany("INSERT INTO Followers VALUES (?,?)", [(0,1),(1,0),(2,0),(2,1)])
assert find_followers_count(c) == [(0,1),(1,1),(2,2)]  # standard case

# No followers
c.execute("DELETE FROM Followers")
c.executemany("INSERT INTO Followers VALUES (?,?)", [])
assert find_followers_count(c) == []  # empty table

# Single user multiple followers
c.execute("DELETE FROM Followers")
c.executemany("INSERT INTO Followers VALUES (?,?)", [(0,1),(0,2),(0,3)])
assert find_followers_count(c) == [(0,3)]  # one user with many followers

# Multiple users, single follower each
c.execute("DELETE FROM Followers")
c.executemany("INSERT INTO Followers VALUES (?,?)", [(0,1),(1,2),(2,3)])
assert find_followers_count(c) == [(0,1),(1,1),(2,1)]  # each user has one follower

Test	Why
Standard example	Validates basic functionality and aggregation
Empty table	Checks handling of zero rows
Single user multiple followers	Ensures counting works with multiple followers for one user
Multiple users, single follower	Ensures grouping works when all users have exactly one follower

Edge Cases

One important edge case is an empty Followers table. The function should return an empty list without errors, which our SQL handles gracefully as GROUP BY over zero rows results in zero output.

A second edge case is a user with no followers. Since the Followers table only contains existing relationships, users with zero followers will not appear in the table, and our function will not include them in the output, which matches the problem specification.

A third edge case is the presence of a single user followed by multiple users or having a single follower. Our implementation handles this by aggregating all rows for the given user_id and correctly counting the number of followers, regardless of how many exist. This ensures that both high and low fan-out scenarios are accounted for accurately.