LeetCode 597 - Friend Requests I: Overall Acceptance Rate

This problem asks us to compute the overall acceptance rate of friend requests in a social network system. Two database tables are provided. The first table, FriendRequest, stores all friend requests that users sent to each other.

leetcodeeasydatabase

LeetCode Problem 597

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to compute the overall acceptance rate of friend requests in a social network system. Two database tables are provided. The first table, FriendRequest, stores all friend requests that users sent to each other. The second table, RequestAccepted, stores requests that were accepted.

The acceptance rate is defined as:

$\text{Acceptance Rate} = \frac{\text{Number of Unique Accepted Requests}}{\text{Number of Unique Friend Requests}}$

The important detail is that both tables may contain duplicate rows. Multiple identical requests between the same pair of users should only be counted once. Similarly, multiple identical acceptances should also only be counted once. Therefore, uniqueness is determined by the pair of users involved.

For example, if user 3 sends two requests to user 4, they still count as only one request. Likewise, if user 4 accepts the request twice, it still counts as only one acceptance.

Another critical point is that accepted requests do not need to exist in the FriendRequest table. Even if an acceptance appears without a corresponding request, it must still be counted in the numerator.

The expected output is a single column named accept_rate, rounded to two decimal places.

The problem also specifies an important edge case. If there are no friend requests at all, the acceptance rate should be 0.00 instead of causing a division-by-zero error.

Because this is a database problem, the primary challenge is not algorithmic complexity in the traditional sense, but correctly handling duplicates and edge conditions using SQL aggregation functions.

Approaches

Brute Force Approach

A brute-force approach would process every row manually and track duplicates using application-side logic. We could iterate through all rows in FriendRequest, store unique (sender_id, send_to_id) pairs in a set, then iterate through RequestAccepted and store unique (requester_id, accepter_id) pairs in another set.

After building both sets, we would compute:

  • Total unique requests
  • Total unique acceptances
  • Acceptance rate

This approach produces the correct result because sets naturally eliminate duplicates. However, it is inefficient and unnecessary in a relational database environment because SQL already provides aggregation and distinct-counting operations optimized for this purpose.

Moving data outside the database layer also increases memory usage and network overhead.

Optimal Approach

The key insight is that we only need counts of unique user pairs from each table. SQL provides COUNT(DISTINCT ...), which allows the database engine to handle duplicate elimination efficiently.

The optimal solution computes:

  • The number of distinct (sender_id, send_to_id) pairs from FriendRequest
  • The number of distinct (requester_id, accepter_id) pairs from RequestAccepted

Then it divides the two values and rounds the result to two decimal places.

We must also guard against division by zero when there are no requests. SQL functions such as IFNULL and NULLIF help handle this cleanly.

Approach Time Complexity Space Complexity Notes
Brute Force O(R + A) O(R + A) Uses external sets to remove duplicates
Optimal O(R + A) O(1) extra Uses SQL aggregation and distinct counting

Here:

  • R is the number of rows in FriendRequest
  • A is the number of rows in RequestAccepted

Algorithm Walkthrough

  1. Count all unique friend requests by selecting distinct (sender_id, send_to_id) pairs from the FriendRequest table. This removes duplicate requests between the same users.
  2. Count all unique accepted requests by selecting distinct (requester_id, accepter_id) pairs from the RequestAccepted table. This removes duplicate acceptances.
  3. Divide the unique acceptance count by the unique request count to compute the acceptance rate.
  4. Use NULLIF(request_count, 0) to avoid division by zero. If the denominator becomes zero, SQL returns NULL instead of throwing an error.
  5. Use IFNULL(..., 0) so that a NULL result becomes 0.
  6. Use ROUND(..., 2) to ensure the result contains exactly two decimal places.

Why it works

The solution works because the problem definition explicitly states that duplicate requests and duplicate acceptances should only be counted once. Using COUNT(DISTINCT ...) guarantees that each unique user pair contributes exactly one count. The final division therefore exactly matches the mathematical definition of the acceptance rate.

Python Solution

# Write your MySQL query statement below

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

The query is divided into three logical sections.

The first subquery counts distinct accepted request pairs from the RequestAccepted table. Because duplicates should only count once, we use COUNT(DISTINCT requester_id, accepter_id).

The second subquery counts distinct request pairs from the FriendRequest table using the same idea.

Next, the denominator is wrapped with NULLIF(..., 0). If there are no requests, the denominator becomes NULL, preventing division-by-zero errors.

The outer IFNULL(..., 0) converts a NULL result into 0, which satisfies the problem requirement.

Finally, ROUND(..., 2) formats the answer to two decimal places.

Go Solution

// Write your MySQL query statement below

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

Because this is a database problem, the solution is identical regardless of whether the LeetCode language selection is Python or Go. The platform expects a SQL query submission, so there are no Go-specific implementation details involving slices, maps, or integer overflow.

Worked Examples

Example 1

Friend requests:

sender_id send_to_id
1 2
1 3
1 4
2 3
3 4

All five rows are unique.

Unique request count:

Unique Pair
(1,2)
(1,3)
(1,4)
(2,3)
(3,4)

Total requests = 5

Accepted requests:

requester_id accepter_id
1 2
1 3
2 3
3 4
3 4

After removing duplicates:

Unique Pair
(1,2)
(1,3)
(2,3)
(3,4)

Total acceptances = 4

Acceptance rate:

$\frac{4}{5} = 0.80$

Final result:

accept_rate
0.80

Complexity Analysis

Measure Complexity Explanation
Time O(R + A) Database scans both tables once
Space O(1) extra Aggregation handled internally by SQL engine

The query performs aggregation over both tables independently. Each table is scanned once to compute distinct user pairs. The database engine may internally use hashing or sorting for duplicate elimination, but from the query perspective, no additional application-level memory structures are created.

Test Cases

# Example from problem statement
# 5 unique requests, 4 unique acceptances
assert round(4 / 5, 2) == 0.80

# No requests at all
# Should return 0.00 instead of division error
assert 0.00 == 0.00

# Duplicate requests should count once
# Requests: (1,2), (1,2)
# Unique request count = 1
assert round(1 / 1, 2) == 1.00

# Duplicate acceptances should count once
# Acceptances: (1,2), (1,2)
# Unique acceptance count = 1
assert round(1 / 1, 2) == 1.00

# Acceptance without original request
# Still counted in numerator
assert round(1 / 2, 2) == 0.50

# Multiple unique requests, no acceptances
assert round(0 / 3, 2) == 0.00

# Single request and single acceptance
assert round(1 / 1, 2) == 1.00

# Large duplicate-heavy dataset
# Only unique pairs matter
assert round(2 / 3, 2) == 0.67
Test Why
Example input Verifies core functionality
No requests Ensures division-by-zero handling
Duplicate requests Validates distinct request counting
Duplicate acceptances Validates distinct acceptance counting
Acceptance without request Confirms numerator logic
No acceptances Ensures zero numerator handled correctly
Single pair Smallest non-empty valid input
Duplicate-heavy dataset Stress-tests distinct aggregation

Edge Cases

One important edge case occurs when the FriendRequest table is completely empty. A naive implementation might attempt to divide by zero, causing a runtime SQL error. This solution avoids that issue by using NULLIF(request_count, 0), which converts a zero denominator into NULL, and then using IFNULL(..., 0) to return 0.00.

Another subtle edge case involves duplicate rows. Because both tables explicitly allow duplicates, using plain COUNT(*) would produce incorrect results. The implementation correctly handles this by counting only distinct user pairs.

A third edge case occurs when an acceptance exists without a corresponding request. The problem statement explicitly says these acceptances should still count. Some implementations mistakenly perform a join between the tables, which would incorrectly discard unmatched acceptances. This solution avoids joins entirely and independently counts unique rows in each table, guaranteeing correctness.