LeetCode 614 - Second Degree Follower

LeetCode Problem 614

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to identify second-degree followers from a social network represented by a single table Follow. The table contains two columns: followee and follower. Each row indicates that a user (follower) follows another user (followee). Importantly, each user cannot follow themselves, and the combination of followee and follower is unique.

A second-degree follower is defined as a user who follows at least one other user and is followed by at least one user. In other words, the user appears both as a follower and as a followee in the table.

The input is a relational table of arbitrary size, where each row is a follower-followee relationship. The expected output is a table with the second-degree followers and the number of followers they have (num), ordered alphabetically by the follower's name.

Constraints tell us that the dataset could be large, so a solution relying on repeated scanning of the table (brute-force joins without filtering) may be inefficient. Also, since a user cannot follow themselves, we do not need to handle self-loops.

Important edge cases include users who only follow but are not followed, users who are only followed but do not follow anyone, and an empty Follow table.

Approaches

The brute-force approach would be to check for each user in the table if they appear as a follower at least once and as a followee at least once. This would require scanning the table multiple times or performing self-joins, which is inefficient for large datasets. While this approach is correct, it does unnecessary repeated work.

The optimal approach leverages SQL aggregation. We first count the number of followers for each user (grouping by followee) and then filter these counts to include only those users who also appear as followers. This ensures that we only consider second-degree followers and avoids repeated scanning of the table. Ordering by follower alphabetically is a straightforward ORDER BY clause.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Repeatedly checks each user across all rows to see if they are both follower and followee.
Optimal	O(n)	O(n)	Aggregates followers by followee, then filters based on existence in follower set; single scan with grouping.

Algorithm Walkthrough

1. Identify all users who are followers by selecting the distinct follower column from the Follow table.
2. Count the number of followers for each user by grouping the table by followee and using COUNT(follower).
3. Filter the counts to include only users that appear in the set of followers identified in step 1. This ensures we only select second-degree followers.
4. Order the resulting rows by the follower column in ascending alphabetical order.

Why it works: This method guarantees correctness because the SQL GROUP BY and COUNT ensure that every user counted has followers. The WHERE clause ensures that the user also follows at least one other user, satisfying both conditions for being a second-degree follower.

Python Solution

import sqlite3
from typing import List, Tuple

def second_degree_followers(conn: sqlite3.Connection) -> List[Tuple[str, int]]:
    query = """
        SELECT f.followee AS follower, COUNT(f.follower) AS num
        FROM Follow f
        WHERE f.followee IN (SELECT DISTINCT follower FROM Follow)
        GROUP BY f.followee
        ORDER BY f.followee
    """
    cursor = conn.cursor()
    cursor.execute(query)
    return cursor.fetchall()

This Python solution leverages SQLite to execute the SQL query directly. First, it creates a subquery that identifies all users who appear as followers. Then, it counts the number of followers for each followee who is also a follower. Finally, it orders the results alphabetically.

Go Solution

package main

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

func SecondDegreeFollowers(db *sql.DB) (*sql.Rows, error) {
    query := `
        SELECT f.followee AS follower, COUNT(f.follower) AS num
        FROM Follow f
        WHERE f.followee IN (SELECT DISTINCT follower FROM Follow)
        GROUP BY f.followee
        ORDER BY f.followee
    `
    return db.Query(query)
}

In Go, the approach is almost identical. The main difference is handling the sql.DB object and returning a *sql.Rows object instead of a list. Go requires explicit error handling and does not allow direct list returns from queries, unlike Python.

Worked Examples

Consider the example table:

+----------+----------+
| followee | follower |
+----------+----------+
| Alice    | Bob      |
| Bob      | Cena     |
| Bob      | Donald   |
| Donald   | Edward   |
+----------+----------+

Step by step:

1. Distinct followers: Bob, Cena, Donald, Edward.
2. Count followers per followee:

• Alice: 1 (Bob)
• Bob: 2 (Cena, Donald)
• Donald: 1 (Edward)

3. Filter followees appearing as followers: Bob, Donald
4. Order alphabetically: Bob, Donald

Output:

+----------+-----+
| follower | num |
+----------+-----+
| Bob      | 2   |
| Donald   | 1   |
+----------+-----+

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single scan of the table with aggregation and filtering using indexes if present
Space	O(n)	Storing counts for each followee and set of distinct followers

The complexity is efficient for large datasets as it avoids nested loops and uses aggregation.

Test Cases

# Basic example from problem
assert second_degree_followers(conn) == [("Bob", 2), ("Donald", 1)]

# Edge case: user follows no one
# Input: only followees with no followers
# Expect: empty list
assert second_degree_followers(conn_empty) == []

# Case: user is follower but has no followers
# Input table: Bob follows Alice, Alice has no followers
# Expect: empty list
assert second_degree_followers(conn_no_followers) == []

# Case: all users are second-degree followers
# Input table:
# Alice->Bob, Bob->Charlie, Charlie->Alice
# Expect: all three counted with respective number of followers
assert second_degree_followers(conn_cyclic) == [("Alice",1),("Bob",1),("Charlie",1)]

Test	Why
Example from problem	Validates core logic of counting second-degree followers
User follows no one	Ensures follower-only users are excluded
Follower without followers	Ensures followee-only users are excluded
All users are second-degree	Tests cyclic follow relationships

Edge Cases

Empty table: The Follow table might have no rows. The algorithm correctly returns an empty result because the subquery for followers and the aggregation will produce no rows.

User with no followers: Users who follow others but are not followed should not appear. This is handled by filtering followees using the set of distinct followers.

Users following multiple users: If a user follows multiple people, they should still be counted once as a second-degree follower. Aggregation counts all their followers correctly, and filtering ensures only second-degree followers are included.

This approach handles these edge cases efficiently and ensures correctness.