LeetCode 1934 - Confirmation Rate

This problem asks us to calculate the confirmation rate for each user in a system where users can request confirmation messages after signing up. We are given two tables: Signups and Confirmations.

leetcodemediumdatabase

LeetCode Problem 1934

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to calculate the confirmation rate for each user in a system where users can request confirmation messages after signing up. We are given two tables: Signups and Confirmations. The Signups table contains all users who signed up, with a unique user_id and a time_stamp of signup. The Confirmations table contains records of each confirmation request made by users, with an action field indicating whether the request was 'confirmed' or 'timeout'.

The goal is to compute the confirmation rate for each user as the number of 'confirmed' requests divided by the total number of requests they made. If a user did not request any confirmations, their confirmation rate is 0. The result should be rounded to two decimal places and returned as a table with user_id and confirmation_rate.

Key points to note are:

  1. Every user in the Confirmations table is guaranteed to exist in Signups due to the foreign key.
  2. Users with no confirmation requests should appear in the output with a rate of 0.
  3. The action column can only be 'confirmed' or 'timeout'.
  4. The result can be returned in any order.
  5. The primary challenge is correctly handling users with zero confirmation requests and ensuring proper rounding.

Important edge cases include users with no confirmations, users with only 'timeout' actions, users with only 'confirmed' actions, and users with a mix of both.

Approaches

Brute Force

The brute-force approach would involve iterating through all users and, for each user, counting the number of 'confirmed' actions and the total number of confirmation requests. For users without confirmations, the rate is set to 0. This approach works but would require scanning the Confirmations table for each user, leading to potentially high time complexity if the number of users or confirmations is large.

Optimal Approach

The optimal approach uses aggregation and joins in SQL. We can group the Confirmations table by user_id to count the total requests and the number of confirmed requests for each user. Then we perform a LEFT JOIN with the Signups table to ensure every user is included, including those with no confirmation requests. Finally, we compute the confirmation rate and round it to two decimal places.

This method ensures a single scan of the Confirmations table and leverages SQL's aggregation functions for efficiency.

Approach Time Complexity Space Complexity Notes
Brute Force O(U * C) O(U) Iterate all users and scan confirmations for each user
Optimal O(C + U) O(U) Aggregate confirmations by user, join with signups, compute rate

Algorithm Walkthrough

  1. Aggregate the Confirmations table by user_id to count total requests (COUNT(*)) and confirmed requests (SUM(CASE WHEN action = 'confirmed' THEN 1 ELSE 0 END)).
  2. Perform a LEFT JOIN with the Signups table to include users without any confirmation requests.
  3. For each user, compute the confirmation rate as confirmed_count / total_count. Use 0 if total_count is null (no requests).
  4. Round the confirmation rate to two decimal places using SQL ROUND function.
  5. Return the result table with user_id and confirmation_rate.

This algorithm works because it ensures all users are included and correctly handles cases where a user has zero confirmation requests.

Python Solution

import sqlite3
from typing import List, Tuple

def confirmation_rate(conn: sqlite3.Connection) -> List[Tuple[int, float]]:
    query = """
    WITH counts AS (
        SELECT
            user_id,
            COUNT(*) AS total_requests,
            SUM(CASE WHEN action = 'confirmed' THEN 1 ELSE 0 END) AS confirmed_count
        FROM Confirmations
        GROUP BY user_id
    )
    SELECT
        s.user_id,
        ROUND(COALESCE(c.confirmed_count, 0) * 1.0 / COALESCE(c.total_requests, 1), 2) AS confirmation_rate
    FROM Signups s
    LEFT JOIN counts c
    ON s.user_id = c.user_id;
    """
    cursor = conn.cursor()
    cursor.execute(query)
    return cursor.fetchall()

In this implementation, we first aggregate confirmation data in a CTE named counts. The LEFT JOIN ensures that users without any confirmation requests appear with a confirmation rate of 0. We use COALESCE to handle null values from the join, preventing division by null. Multiplying by 1.0 ensures float division, and rounding to two decimal places matches the problem requirements.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
)

func ConfirmationRate(db *sql.DB) (*sql.Rows, error) {
    query := `
    WITH counts AS (
        SELECT
            user_id,
            COUNT(*) AS total_requests,
            SUM(CASE WHEN action = 'confirmed' THEN 1 ELSE 0 END) AS confirmed_count
        FROM Confirmations
        GROUP BY user_id
    )
    SELECT
        s.user_id,
        ROUND(COALESCE(c.confirmed_count, 0) * 1.0 / COALESCE(c.total_requests, 1), 2) AS confirmation_rate
    FROM Signups s
    LEFT JOIN counts c
    ON s.user_id = c.user_id;
    `
    return db.Query(query)
}

The Go implementation closely mirrors the Python SQL logic. We return *sql.Rows directly, which can be scanned by the caller. The key difference is Go’s use of database/sql package; the SQL query itself remains the same.

Worked Examples

For the provided input:

user_id Confirmed Total Requests Rate
6 0 0 0.00
3 0 2 0.00
7 3 3 1.00
2 1 2 0.50
  1. Aggregate confirmations:
  • User 2 → confirmed_count = 1, total_requests = 2
  • User 3 → confirmed_count = 0, total_requests = 2
  • User 7 → confirmed_count = 3, total_requests = 3
  1. Join with Signups: User 6 has no confirmations → total_requests = 0, confirmed_count = 0
  2. Compute confirmation_rate = confirmed_count / total_requests, using 0 for users with no requests.
  3. Round to 2 decimals.

Complexity Analysis

Measure Complexity Explanation
Time O(C + U) Scan all confirmations to aggregate counts (C = # of confirmation rows), scan all signups for join (U = # of users)
Space O(U) Store aggregate counts per user

The linear complexity ensures the solution scales well even for large datasets.

Test Cases

# test cases
assert confirmation_rate([
    (3, '2020-03-21 10:16:13'),
    (7, '2020-01-04 13:57:59'),
    (2, '2020-07-29 23:09:44'),
    (6, '2020-12-09 10:39:37')
], [
    (3, '2021-01-06 03:30:46', 'timeout'),
    (3, '2021-07-14 14:00:00', 'timeout'),
    (7, '2021-06-12 11:57:29', 'confirmed'),
    (7, '2021-06-13 12:58:28', 'confirmed'),
    (7, '2021-06-14 13:59:27', 'confirmed'),
    (2, '2021-01-22 00:00:00', 'confirmed'),
    (2, '2021-02-28 23:59:59', 'timeout')
]) == [
    (6, 0.00),
    (3, 0.00),
    (7, 1.00),
    (2, 0.50)
]  # Provided example

assert confirmation_rate([], []) == []  # No users, no confirmations

assert confirmation_rate([(1,'2023-01-01 00:00:00')], []) == [(1, 0.00)]  # Single user, no confirmation requests
Test Why
Provided example Validates handling of confirmed, timeout, mixed, and no requests
Empty tables Ensures algorithm handles no data gracefully
Single user with no confirmations Edge case for zero-request users

Edge Cases

  1. User with no confirmation requests: Users who exist in Signups but not in Confirmations should have a confirmation rate of 0. This is handled with a LEFT JOIN and COALESCE in the SQL query.
  2. User with only timeout actions: Users who requested confirmations but none were confirmed should get a confirmation rate of 0. The aggregation logic correctly counts confirmed actions and divides by total requests.
  3. Rounding precision: The problem requires rounding to two decimal places. Using SQL