# LeetCode 602: Friend Requests II: Who Has the Most Friends

## Problem Restatement

We are given a table called `RequestAccepted`.

Each row means one friend request was accepted.

| Column | Type | Meaning |
|---|---|---|
| `requester_id` | int | The user who sent the friend request |
| `accepter_id` | int | The user who accepted the friend request |
| `accept_date` | date | The date when the request was accepted |

We need to find the user who has the most friends and return:

| Column | Meaning |
|---|---|
| `id` | The user id |
| `num` | The number of friends that user has |

The test cases guarantee that only one person has the most friends. The problem also asks a follow-up where multiple people may tie for the most friends. The main solution only needs to return one user because the official test cases guarantee a unique answer. [Source](https://leetcode.com/problems/friend-requests-ii-who-has-the-most-friends/)

## Input and Output

Input table:

```sql
RequestAccepted
```

Output columns:

```sql
id, num
```

Each accepted request creates one friendship between two users.

So if this row exists:

```text
requester_id = 1, accepter_id = 2
```

then user `1` has user `2` as a friend, and user `2` has user `1` as a friend.

Both sides must be counted.

## Example

Input:

| requester_id | accepter_id | accept_date |
|---:|---:|---|
| 1 | 2 | 2016-06-03 |
| 1 | 3 | 2016-06-08 |
| 2 | 3 | 2016-06-08 |
| 3 | 4 | 2016-06-09 |

Friend counts:

| User | Friends | Count |
|---:|---|---:|
| 1 | 2, 3 | 2 |
| 2 | 1, 3 | 2 |
| 3 | 1, 2, 4 | 3 |
| 4 | 3 | 1 |

User `3` has the most friends.

Output:

| id | num |
|---:|---:|
| 3 | 3 |

## First Thought: Count Requesters Only

A first attempt might count how many times each user appears in `requester_id`.

```sql
SELECT requester_id, COUNT(*)
FROM RequestAccepted
GROUP BY requester_id;
```

This is incomplete.

A user can have friends from both sides of the table:

| Role | Meaning |
|---|---|
| `requester_id` | The user sent a request that was accepted |
| `accepter_id` | The user accepted a request from someone else |

Both roles represent friendship.

So we need to count every appearance of a user in either column.

## Key Insight

Each accepted request contributes one friend count to both users.

For this row:

| requester_id | accepter_id |
|---:|---:|
| 1 | 3 |

we should count:

| id | Contribution |
|---:|---:|
| 1 | 1 |
| 3 | 1 |

The clean way is to convert both columns into one column named `id`.

We can do that with `UNION ALL`.

```sql
SELECT requester_id AS id
FROM RequestAccepted

UNION ALL

SELECT accepter_id AS id
FROM RequestAccepted
```

After this transformation, each row means:

“This user has one friend contribution.”

Then we group by `id` and count rows.

## Algorithm

First, select all requesters as user ids.

Second, select all accepters as user ids.

Third, combine them with `UNION ALL`.

Fourth, group by user id and count how many times each user appears.

Fifth, sort by the count in descending order.

Finally, return the first row.

## SQL Solution

```sql
SELECT
    id,
    COUNT(*) AS num
FROM (
    SELECT requester_id AS id
    FROM RequestAccepted

    UNION ALL

    SELECT accepter_id AS id
    FROM RequestAccepted
) AS friends
GROUP BY id
ORDER BY num DESC
LIMIT 1;
```

## Code Explanation

The inner query creates one unified list of user ids:

```sql
SELECT requester_id AS id
FROM RequestAccepted

UNION ALL

SELECT accepter_id AS id
FROM RequestAccepted
```

We use `UNION ALL`, not `UNION`.

`UNION ALL` keeps every row. That matters because every accepted request contributes to the friend count.

If user `3` appears three times across both columns, we need all three appearances to remain.

The outer query groups the unified list:

```sql
GROUP BY id
```

Then it counts how many rows each user has:

```sql
COUNT(*) AS num
```

This count is the total number of friends for that user.

Then we sort from largest to smallest:

```sql
ORDER BY num DESC
```

Because the problem guarantees one unique user with the most friends, we can return only the first row:

```sql
LIMIT 1
```

## Correctness

Each row in `RequestAccepted` represents one accepted friendship between `requester_id` and `accepter_id`.

The inner query emits one row for the requester and one row for the accepter. Therefore, each friendship contributes exactly one count to each of its two users.

After the `UNION ALL`, every emitted row represents one friend contribution for one user.

The outer query groups these contributions by user id. Therefore, `COUNT(*)` gives the total number of friends for each user.

Sorting by this count in descending order places the user with the largest friend count first.

Since the test cases guarantee that only one person has the most friends, `LIMIT 1` returns exactly the required user and friend count.

## Complexity

Let `n` be the number of rows in `RequestAccepted`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | The database groups and sorts user counts |
| Space | `O(n)` | The derived table contains two rows per friendship |

The derived table has `2n` rows because every friendship contributes one row for each user.

## Follow-up: Return All Ties

In the real world, multiple users may have the same maximum number of friends.

For that version, we can rank users by friend count and return every user whose rank is `1`.

```sql
WITH friend_counts AS (
    SELECT
        id,
        COUNT(*) AS num
    FROM (
        SELECT requester_id AS id
        FROM RequestAccepted

        UNION ALL

        SELECT accepter_id AS id
        FROM RequestAccepted
    ) AS friends
    GROUP BY id
),
ranked AS (
    SELECT
        id,
        num,
        DENSE_RANK() OVER (ORDER BY num DESC) AS rnk
    FROM friend_counts
)
SELECT
    id,
    num
FROM ranked
WHERE rnk = 1;
```

## Testing

Sample data:

```sql
CREATE TABLE RequestAccepted (
    requester_id INT,
    accepter_id INT,
    accept_date DATE
);

INSERT INTO RequestAccepted (requester_id, accepter_id, accept_date) VALUES
    (1, 2, '2016-06-03'),
    (1, 3, '2016-06-08'),
    (2, 3, '2016-06-08'),
    (3, 4, '2016-06-09');
```

Expected output:

| id | num |
|---:|---:|
| 3 | 3 |

Additional case:

```sql
TRUNCATE TABLE RequestAccepted;

INSERT INTO RequestAccepted (requester_id, accepter_id, accept_date) VALUES
    (1, 2, '2020-01-01'),
    (2, 3, '2020-01-02'),
    (2, 4, '2020-01-03');
```

Friend counts:

| User | Count |
|---:|---:|
| 1 | 1 |
| 2 | 3 |
| 3 | 1 |
| 4 | 1 |

Expected output:

| id | num |
|---:|---:|
| 2 | 3 |