LeetCode 614: Second Degree Follower

Problem Restatement

We are given a table called Follow.

Each row means one user follows another user.

The pair (followee, follower) is the primary key.

A second-degree follower is a user who:

1. follows at least one user
2. is followed by at least one user

We need to return every second-degree follower and the number of people who follow them.

The result should be ordered by follower alphabetically. The official statement defines a second-degree follower this way and asks for the number of their followers.

Input and Output

Input table:

Follow

Output columns:

follower, num

Here, the output column follower means the user who is a second-degree follower.

The output column num means how many users follow that person.

Example

Input:

Relationships:

Now classify users:

Bob has two followers: Cena and Donald.

Donald has one follower: Edward.

Output:

First Thought: Count Followers for Every User

A first query might count how many followers each user has:

SELECT
    followee AS follower,
    COUNT(*) AS num
FROM Follow
GROUP BY followee;

This counts followers correctly, but it includes users who do not follow anyone.

For example, Alice has one follower, Bob, but Alice does not follow anyone. So Alice should not appear in the result.

We need one extra condition: the user must also appear in the follower column.

Key Insight

A second-degree follower must appear in both roles:

So we can join the table with itself.

Use one copy to represent the person following someone:

f1.follower

Use another copy to represent people following that same person:

f2.followee

The join condition is:

f1.follower = f2.followee

This means:

“The user who follows someone in f1 is also followed by someone in f2.”

Then we count how many followers that user has.

Algorithm

Join Follow with itself.

For each user who appears as both a follower and a followee:

1. Group by that user.
2. Count distinct people who follow that user.
3. Return the user and the count.
4. Order by the user name alphabetically.

SQL Solution

SELECT
    f1.follower,
    COUNT(DISTINCT f2.follower) AS num
FROM Follow AS f1
JOIN Follow AS f2
    ON f1.follower = f2.followee
GROUP BY f1.follower
ORDER BY f1.follower;

Code Explanation

The first table alias, f1, identifies users who follow at least one person:

FROM Follow AS f1

Every value in f1.follower is a user who follows someone.

The second table alias, f2, identifies users who have followers:

JOIN Follow AS f2
    ON f1.follower = f2.followee

The condition says that the same user from f1.follower must also appear as a followee in another row.

That means the user both follows someone and is followed by someone.

Then we count that user’s followers:

COUNT(DISTINCT f2.follower) AS num

We use DISTINCT to avoid overcounting when the same user appears multiple times in f1 because they follow multiple people.

Finally:

GROUP BY f1.follower
ORDER BY f1.follower

groups by the second-degree follower and sorts the output alphabetically.

Correctness

A user appears in the result only if the join condition finds at least one row where the user is a follower and at least one row where the same user is a followee.

Therefore, every returned user follows at least one user and is followed by at least one user, which exactly matches the definition of a second-degree follower.

For each returned user, the rows from f2 are precisely the rows where that user is the followee. Each such row represents one person following that user. Therefore, counting f2.follower gives the number of followers that user has.

Using COUNT(DISTINCT f2.follower) prevents duplicate counting caused by multiple f1 rows for the same user.

So the query returns exactly each second-degree follower and their follower count.

Complexity

Let n be the number of rows in Follow.

With indexes on follower and followee, the database can execute the join much more efficiently.

Alternative: IN Subquery

We can also solve it by first counting followers for every followee, then keeping only users who also appear as a follower.

SELECT
    followee AS follower,
    COUNT(*) AS num
FROM Follow
WHERE followee IN (
    SELECT DISTINCT follower
    FROM Follow
)
GROUP BY followee
ORDER BY follower;

This version is compact.

It says:

“Count followers for each user, but only for users who themselves follow someone.”

Testing

Sample data:

CREATE TABLE Follow (
    followee VARCHAR(255),
    follower VARCHAR(255),
    PRIMARY KEY (followee, follower)
);

INSERT INTO Follow (followee, follower) VALUES
    ('Alice', 'Bob'),
    ('Bob', 'Cena'),
    ('Bob', 'Donald'),
    ('Donald', 'Edward');

Expected output:

Additional case:

TRUNCATE TABLE Follow;

INSERT INTO Follow (followee, follower) VALUES
    ('A', 'B'),
    ('A', 'C'),
    ('B', 'D'),
    ('C', 'D'),
    ('D', 'E');

User B follows A and has follower D.

User C follows A and has follower D.

User D follows B and C, and has follower E.

Expected output: