LeetCode 1633 - Percentage of Users Attended a Contest

This problem asks us to calculate the percentage of users who attended each contest. We are given two tables: Users and

leetcodeeasydatabase

LeetCode Problem 1633

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to calculate the percentage of users who attended each contest. We are given two tables: Users and Register. The Users table contains all users, each with a unique user_id. The Register table contains records of which user registered for which contest, using contest_id and user_id.

The goal is to compute the number of unique users registered in each contest, divide it by the total number of users, multiply by 100, and round the result to two decimal places. The final output must be sorted first by percentage in descending order, and in the event of a tie, by contest_id in ascending order.

Important constraints and observations include that user_id is unique, (contest_id, user_id) is unique, and there are no missing values. Edge cases that could trip up naive solutions include contests with zero registrations, rounding issues, and ordering ties.

Approaches

The brute-force approach would iterate through each contest, count the number of users registered, calculate the percentage for each, and then sort the results. While straightforward, it requires scanning the entire Register table multiple times if implemented naively, which is inefficient for large datasets.

The optimal approach leverages SQL aggregation functions. The key insight is that we can count the number of users per contest using COUNT(user_id) grouped by contest_id, and compute the percentage using the total number of users obtained from Users. This avoids multiple scans and simplifies the solution into a single query. Rounding and ordering can then be applied at the end.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(k) For each contest, count registrations iteratively; n = users, m = registrations, k = contests
Optimal O(n + m) O(k) Aggregate with SQL GROUP BY, count per contest, and compute percentage in one pass

Algorithm Walkthrough

  1. Count total users: Retrieve the total number of users from the Users table using COUNT(*). This represents the denominator for our percentage calculation.
  2. Count users per contest: Aggregate the Register table by contest_id using COUNT(user_id) to get the number of registered users per contest.
  3. Compute percentage: For each contest, divide the count of registered users by the total user count and multiply by 100. Use rounding to ensure the result has two decimal places.
  4. Sort results: Order the final results first by percentage in descending order, and then by contest_id in ascending order for ties.

Why it works: Counting users per contest and dividing by the total guarantees accurate percentages because the total number of users is constant. SQL aggregation ensures each contest is handled independently, and ordering ensures correct presentation.

Python Solution

import sqlite3

def percentage_users_attended(db: sqlite3.Connection):
    query = """
    WITH total_users AS (
        SELECT COUNT(*) AS total FROM Users
    )
    SELECT
        r.contest_id,
        ROUND(COUNT(r.user_id) * 100.0 / t.total, 2) AS percentage
    FROM Register r
    CROSS JOIN total_users t
    GROUP BY r.contest_id
    ORDER BY percentage DESC, contest_id ASC
    """
    cursor = db.cursor()
    cursor.execute(query)
    return cursor.fetchall()

Explanation:

We first compute total_users as a CTE to hold the total number of users. Then, we aggregate the Register table by contest_id and compute the percentage for each contest. ROUND ensures the two-decimal requirement, and CROSS JOIN allows access to the total count without subqueries in each row. Finally, we sort the results per the problem requirements.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/go-sql-driver/mysql"
    "fmt"
)

func PercentageUsersAttended(db *sql.DB) ([]struct {
    ContestID  int
    Percentage float64
}, error) {
    query := `
    WITH total_users AS (
        SELECT COUNT(*) AS total FROM Users
    )
    SELECT
        r.contest_id,
        ROUND(COUNT(r.user_id) * 100.0 / t.total, 2) AS percentage
    FROM Register r
    CROSS JOIN total_users t
    GROUP BY r.contest_id
    ORDER BY percentage DESC, contest_id ASC
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []struct {
        ContestID  int
        Percentage float64
    }

    for rows.Next() {
        var contestID int
        var percentage float64
        if err := rows.Scan(&contestID, &percentage); err != nil {
            return nil, err
        }
        results = append(results, struct {
            ContestID  int
            Percentage float64
        }{contestID, percentage})
    }
    return results, nil
}

Go-specific notes:

In Go, we define a slice of structs to hold results. db.Query executes the SQL, and we iterate over rows using rows.Next(). Scan maps the result columns into Go variables. We use ROUND in SQL to ensure two-decimal accuracy, avoiding any post-processing in Go.

Worked Examples

Using the example from the problem:

contest_id registered_users percentage
208 3 100.0
209 3 100.0
210 3 100.0
215 2 66.67
207 1 33.33

Steps:

  1. Total users = 3
  2. Count per contest: 208 -> 3, 209 -> 3, 210 -> 3, 215 -> 2, 207 -> 1
  3. Compute percentage: (count / 3) * 100, round to 2 decimals
  4. Sort by percentage descending and contest_id ascending for ties

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) n = number of users, m = number of registrations; counting users and aggregating registrations are linear operations
Space O(k) k = number of contests; storing aggregated counts per contest

This is optimal because we only scan the users table once and the register table once. Sorting is on the number of contests, which is typically much smaller than the total rows.

Test Cases

# test cases
# basic example
assert percentage_users_attended(db) == [(208, 100.0), (209, 100.0), (210, 100.0), (215, 66.67), (207, 33.33)]

# single user, single contest
assert percentage_users_attended(single_user_db) == [(1, 100.0)]

# contest with no users should not appear
assert percentage_users_attended(no_registration_db) == []

# tie on percentage, sorted by contest_id ascending
assert percentage_users_attended(tie_percentage_db) == [(101, 50.0), (102, 50.0)]
Test Why
Basic example Validates main example logic and rounding
Single user Edge case with 100% attendance
No registration Contests with no users should not appear
Tie on percentage Checks secondary sort order by contest_id

Edge Cases

No registrations: If a contest has no registrations, it should not appear in the output. Using GROUP BY on the Register table naturally excludes such contests.

All users registered in a contest: This results in a percentage of 100. Correct rounding is crucial, and the solution handles this using ROUND.

Rounding precision: If the percentage has more than two decimals, rounding can lead to edge cases like 66.666... becoming 66.67. Using SQL's ROUND function guarantees two-decimal accuracy.

Tie in percentage: Multiple contests with the same percentage must be sorted by contest_id ascending. This is explicitly handled in the ORDER BY clause.

This approach ensures all edge cases are handled correctly without additional logic.