Solution Explanation for LeetCode 597: Friend Requests I: Overall Acceptance Rate

This problem requires calculating the overall acceptance rate of friend requests from two tables: FriendRequest and RequestAccepted. The acceptance rate is the number of unique accepted requests divided by the number of unique sent requests.

Approach

The solution involves these steps:

1. Counting Unique Accepted Requests: We need to count the number of unique accepted requests from the RequestAccepted table. We use COUNT(DISTINCT requester_id, accepter_id) to avoid counting duplicate accepted requests.

2. Counting Unique Sent Requests: We need to count the number of unique sent requests from the FriendRequest table. Similarly, we use COUNT(DISTINCT sender_id, send_to_id) to avoid duplicates.

3. Calculating the Acceptance Rate: We divide the count of unique accepted requests by the count of unique sent requests. We handle the case where there are no requests (division by zero) using IFNULL() in MySQL, which returns 0 if the first argument is NULL.

4. Rounding the Result: Finally, we round the acceptance rate to two decimal places using ROUND().

MySQL Code and Explanation

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

• SELECT COUNT(DISTINCT requester_id, accepter_id) FROM RequestAccepted: This subquery counts the number of unique accepted requests. DISTINCT ensures that each unique pair (requester_id, accepter_id) is counted only once.

• SELECT COUNT(DISTINCT sender_id, send_to_id) FROM FriendRequest: This subquery counts the number of unique sent requests. DISTINCT avoids double counting.

• /: The division operator calculates the acceptance rate.

• IFNULL(..., 0): This handles the case where there are no friend requests (FriendRequest table is empty). If the division results in a NULL value (due to division by zero), it replaces it with 0.

• ROUND(..., 2): This rounds the result to two decimal places.

• AS accept_rate: This assigns the alias "accept_rate" to the calculated column.

Time Complexity Analysis

The time complexity of this SQL query is dominated by the two COUNT(DISTINCT ...) subqueries. The COUNT(DISTINCT) operation generally has a time complexity that depends on the database system's implementation, but it's often O(N log N) or even O(N) in optimized implementations for certain database systems, where N is the number of rows in the respective table. Therefore, the overall time complexity is approximately O(M log M + K log K), where M is the number of rows in RequestAccepted and K is the number of rows in FriendRequest. The remaining operations (division and rounding) are constant time.

Space Complexity Analysis

The space complexity is primarily determined by the temporary space used by the database system during the execution of the COUNT(DISTINCT) operations. This space complexity is typically proportional to the number of unique pairs in each table, making it approximately O(M' + K'), where M' and K' represent the number of unique (requester_id, accepter_id) and (sender_id, send_to_id) pairs respectively. This is generally less than the number of rows in each table.