# LeetCode 614: Second Degree Follower

## Problem Restatement

We are given a table called `Follow`.

Each row means one user follows another user.

| Column | Type | Meaning |
|---|---|---|
| `followee` | varchar | The user being followed |
| `follower` | varchar | The user who follows `followee` |

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:

```sql
Follow
```

Output columns:

```sql
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:

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

Relationships:

| Row | Meaning |
|---|---|
| Alice, Bob | Bob follows Alice |
| Bob, Cena | Cena follows Bob |
| Bob, Donald | Donald follows Bob |
| Donald, Edward | Edward follows Donald |

Now classify users:

| User | Follows Someone? | Has Followers? | Second-Degree Follower? |
|---|---|---|---|
| Alice | No | Yes | No |
| Bob | Yes | Yes | Yes |
| Cena | Yes | No | No |
| Donald | Yes | Yes | Yes |
| Edward | Yes | No | No |

Bob has two followers: Cena and Donald.

Donald has one follower: Edward.

Output:

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

## First Thought: Count Followers for Every User

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

```sql
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:

| Role | Column |
|---|---|
| They follow someone | `follower` |
| Someone follows them | `followee` |

So we can join the table with itself.

Use one copy to represent the person following someone:

```sql
f1.follower
```

Use another copy to represent people following that same person:

```sql
f2.followee
```

The join condition is:

```sql
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

```sql
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:

```sql
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:

```sql
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:

```sql
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:

```sql
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`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` worst case | A self join may compare many pairs |
| Space | `O(n)` | Grouping stores one row per qualifying user |

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`.

```sql
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:

```sql
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:

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

Additional case:

```sql
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:

| follower | num |
|---|---:|
| B | 1 |
| C | 1 |
| D | 1 |