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:

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, github.com)

Tables

FriendRequest

This table may contain duplicates.

RequestAccepted

This table may contain duplicates.

Example

Input:

FriendRequest

RequestAccepted

Output:

There are 5 unique sent requests.

There are 4 unique accepted requests:

(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:

4 / 5 = 0.80

First Thought: Count Rows Directly

A first attempt might be:

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:

(sender_id, send_to_id)

For accepted requests, the unique pair is:

(requester_id, accepter_id)

So the numerator is:

COUNT(DISTINCT requester_id, accepter_id)

and the denominator is:

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:

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

The exact execution plan depends on the SQL engine.

Implementation

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:

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:

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:

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.

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:

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:

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:

Additional test cases: