# LeetCode 597: Friend Requests I: Overall Acceptance Rate

## Problem Restatement

We are given two tables: `FriendRequest` and `RequestAccepted`.

`FriendRequest` records friend requests sent from one user to another.

`RequestAccepted` records accepted friend requests.

We need to compute the overall acceptance rate:

```text
number of unique accepted requests / number of unique sent requests
```

The result should be rounded to two decimal places and returned as `accept_rate`.

Important details:

1. Duplicate requests between the same sender and receiver count only once.
2. Duplicate acceptances between the same requester and accepter count only once.
3. Accepted requests do not necessarily have to appear in the original request table.
4. If there are no requests, return `0.00`. The official statement uses these two tables and asks for the overall acceptance rate rounded to two decimals. ([leetcode.com](https://leetcode.com/problems/friend-requests-i-overall-acceptance-rate/), [github.com](https://github.com/doocs/leetcode/blob/main/solution/0500-0599/0597.Friend%20Requests%20I%20Overall%20Acceptance%20Rate/README_EN.md))

## Tables

### FriendRequest

| Column | Type | Meaning |
|---|---|---|
| `sender_id` | int | User who sent the friend request |
| `send_to_id` | int | User who received the friend request |
| `request_date` | date | Date when the request was sent |

This table may contain duplicates.

### RequestAccepted

| Column | Type | Meaning |
|---|---|---|
| `requester_id` | int | User who sent the original request |
| `accepter_id` | int | User who accepted the request |
| `accept_date` | date | Date when the request was accepted |

This table may contain duplicates.

## Example

Input:

`FriendRequest`

| sender_id | send_to_id | request_date |
|---:|---:|---|
| 1 | 2 | 2016-06-01 |
| 1 | 3 | 2016-06-01 |
| 1 | 4 | 2016-06-01 |
| 2 | 3 | 2016-06-02 |
| 3 | 4 | 2016-06-09 |

`RequestAccepted`

| 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 |
| 3 | 4 | 2016-06-10 |

Output:

| accept_rate |
|---:|
| 0.80 |

There are `5` unique sent requests.

There are `4` unique accepted requests:

```text
(1, 2)
(1, 3)
(2, 3)
(3, 4)
```

The pair `(3, 4)` appears twice in `RequestAccepted`, but it counts once.

So the acceptance rate is:

```text
4 / 5 = 0.80
```

## First Thought: Count Rows Directly

A first attempt might be:

```sql
SELECT
    ROUND(
        (SELECT COUNT(*) FROM RequestAccepted)
        /
        (SELECT COUNT(*) FROM FriendRequest),
        2
    ) AS accept_rate;
```

This is not correct because both tables may contain duplicates.

If the same user sends the same request multiple times, it should count once.

If the same request is accepted multiple times, it should count once.

So we need `COUNT(DISTINCT ...)`, not `COUNT(*)`.

## Key Insight

Each request is identified by a pair of users.

For sent requests, the unique pair is:

```text
(sender_id, send_to_id)
```

For accepted requests, the unique pair is:

```text
(requester_id, accepter_id)
```

So the numerator is:

```sql
COUNT(DISTINCT requester_id, accepter_id)
```

and the denominator is:

```sql
COUNT(DISTINCT sender_id, send_to_id)
```

Then we divide and round to two decimal places.

We also need to avoid division by zero when there are no sent requests.

## Algorithm

1. Count unique sent request pairs from `FriendRequest`.
2. Count unique accepted request pairs from `RequestAccepted`.
3. If the request count is `0`, return `0.00`.
4. Otherwise, return the accepted count divided by the request count.
5. Round the result to two decimal places.

## Correctness

The request count subquery counts distinct `(sender_id, send_to_id)` pairs. Therefore, it counts every unique sent friend request exactly once, even if the table contains duplicates.

The accepted count subquery counts distinct `(requester_id, accepter_id)` pairs. Therefore, it counts every unique accepted request exactly once, even if the table contains duplicate acceptances.

The problem defines the acceptance rate as the number of unique accepted requests divided by the number of unique sent requests. The query computes exactly those two values and divides them.

If there are no sent requests, the problem requires `0.00`. The query handles that case explicitly.

Therefore, the query returns the required acceptance rate.

## Complexity

Let:

```text
R = number of rows in FriendRequest
A = number of rows in RequestAccepted
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(R + A)` to `O(R log R + A log A)` | Depends on how the database computes distinct pairs |
| Space | `O(R + A)` | Distinct aggregation may store unique request and accepted pairs |

The exact execution plan depends on the SQL engine.

## Implementation

```sql
WITH request_count AS (
    SELECT COUNT(DISTINCT sender_id, send_to_id) AS total_requests
    FROM FriendRequest
),
accepted_count AS (
    SELECT COUNT(DISTINCT requester_id, accepter_id) AS total_accepted
    FROM RequestAccepted
)
SELECT
    CASE
        WHEN total_requests = 0 THEN 0.00
        ELSE ROUND(total_accepted / total_requests, 2)
    END AS accept_rate
FROM request_count, accepted_count;
```

## Code Explanation

This CTE counts unique sent requests:

```sql
WITH request_count AS (
    SELECT COUNT(DISTINCT sender_id, send_to_id) AS total_requests
    FROM FriendRequest
)
```

The pair `(sender_id, send_to_id)` identifies one request relationship.

This CTE counts unique accepted requests:

```sql
accepted_count AS (
    SELECT COUNT(DISTINCT requester_id, accepter_id) AS total_accepted
    FROM RequestAccepted
)
```

The pair `(requester_id, accepter_id)` identifies one accepted relationship.

The final query handles the zero-request case:

```sql
CASE
    WHEN total_requests = 0 THEN 0.00
    ELSE ROUND(total_accepted / total_requests, 2)
END AS accept_rate
```

If there are no requests, returning `0.00` avoids division by zero and matches the problem requirement.

Otherwise, the query divides accepted requests by sent requests and rounds the result.

## Compact MySQL Version

A shorter version uses scalar subqueries.

```sql
SELECT
    IFNULL(
        ROUND(
            (SELECT COUNT(DISTINCT requester_id, accepter_id)
             FROM RequestAccepted)
            /
            (SELECT COUNT(DISTINCT sender_id, send_to_id)
             FROM FriendRequest),
            2
        ),
        0.00
    ) AS accept_rate;
```

If the denominator is zero, the division returns `NULL`, and `IFNULL` returns `0.00`.

## Testing

Sample data:

```sql
CREATE TABLE FriendRequest (
    sender_id INT,
    send_to_id INT,
    request_date DATE
);

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

INSERT INTO FriendRequest (sender_id, send_to_id, request_date) VALUES
(1, 2, '2016-06-01'),
(1, 3, '2016-06-01'),
(1, 4, '2016-06-01'),
(2, 3, '2016-06-02'),
(3, 4, '2016-06-09');

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'),
(3, 4, '2016-06-10');
```

Query:

```sql
WITH request_count AS (
    SELECT COUNT(DISTINCT sender_id, send_to_id) AS total_requests
    FROM FriendRequest
),
accepted_count AS (
    SELECT COUNT(DISTINCT requester_id, accepter_id) AS total_accepted
    FROM RequestAccepted
)
SELECT
    CASE
        WHEN total_requests = 0 THEN 0.00
        ELSE ROUND(total_accepted / total_requests, 2)
    END AS accept_rate
FROM request_count, accepted_count;
```

Expected result:

| accept_rate |
|---:|
| 0.80 |

Additional test cases:

| Case | Expected behavior |
|---|---|
| Duplicate sent request | Counted once |
| Duplicate accepted request | Counted once |
| Accepted pair missing from request table | Still counted in numerator |
| No rows in `FriendRequest` | Return `0.00` |
| No rows in `RequestAccepted` | Return `0.00` if requests exist |