LeetCode 3308 - Find Top Performing Driver

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to identify the top-performing driver for each fuel type based on the trips data. We are given three tables: Drivers, Vehicles, and Trips. Each driver may operate one or more vehicles, and each vehicle may have multiple trips. The goal is to compute, for each fuel type, the driver with the highest average rating from all their trips. If there is a tie in average rating, the driver with the longest total distance traveled wins. If there is still a tie, the driver with the fewest accidents wins. The final output should list the fuel_type, driver_id, average rating (rounded to 2 decimal places), and total distance, ordered by fuel_type ascending.

Inputs represent driver profiles, vehicles associated with those drivers, and trip records for each vehicle. The output consolidates these tables to give a single “best driver” per fuel type. Important constraints include the need to round the average rating to 2 decimals and handle ties in a specific priority order. Edge cases include drivers with no trips, multiple drivers with the same rating and distance, and vehicles that may share fuel types.

Approaches

The brute-force approach would join all three tables (Drivers, Vehicles, Trips) and compute the average rating and total distance for each driver per fuel type. Then, for each fuel type, we would sort all drivers according to the ranking rules (average rating descending, distance descending, accidents ascending) and select the first driver. This works, but it involves sorting potentially large datasets multiple times, which can be inefficient.

The optimal approach leverages SQL window functions to rank drivers within each fuel type directly after aggregation. First, we join the tables and compute the total distance and average rating per driver per fuel type. Then, we use the ROW_NUMBER() function ordered by rating, distance, and accidents to select only the top driver for each fuel type. This reduces unnecessary sorting and ensures we efficiently select a single row per fuel type.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N log N)	O(N)	Join tables, aggregate per driver, sort per fuel type, pick top
Optimal	O(N)	O(N)	Aggregate per driver and rank using window functions, select top driver per fuel type

Algorithm Walkthrough

Join the tables: Combine Drivers, Vehicles, and Trips on driver_id and vehicle_id to associate each trip with the driver and fuel type.
Aggregate per driver and fuel type: Compute the total distance traveled and the average rating for each driver grouped by fuel type.
Round the average rating: Round the computed average rating to 2 decimal places to comply with output format.
Rank drivers within each fuel type: Use the SQL ROW_NUMBER() function partitioned by fuel_type and ordered by average_rating descending, total_distance descending, and accidents ascending. This assigns a unique rank to each driver within each fuel type.
Select top drivers: Filter rows where the rank equals 1, which gives the top-performing driver per fuel type.
Order the result: Finally, sort the resulting table by fuel_type in ascending order.

Why it works: The aggregation computes the required metrics per driver. Using a window function ensures that ties are broken according to the problem specification. Selecting only rank 1 ensures that only the top driver per fuel type is returned.

Python Solution

class Solution:
    def topDriverPerFuel(self) -> str:
        return """
        WITH DriverStats AS (
            SELECT
                v.fuel_type,
                d.driver_id,
                ROUND(AVG(t.rating), 2) AS rating,
                SUM(t.distance) AS distance,
                d.accidents
            FROM Drivers d
            JOIN Vehicles v ON d.driver_id = v.driver_id
            JOIN Trips t ON v.vehicle_id = t.vehicle_id
            GROUP BY v.fuel_type, d.driver_id, d.accidents
        ),
        RankedDrivers AS (
            SELECT
                fuel_type,
                driver_id,
                rating,
                distance,
                ROW_NUMBER() OVER (
                    PARTITION BY fuel_type
                    ORDER BY rating DESC, distance DESC, accidents ASC
                ) AS rn
            FROM DriverStats
        )
        SELECT
            fuel_type,
            driver_id,
            rating,
            distance
        FROM RankedDrivers
        WHERE rn = 1
        ORDER BY fuel_type ASC;
        """

The Python solution is essentially a wrapper returning the SQL query because this is a Database problem on LeetCode, and the expected submission is SQL. The query joins all relevant tables, computes aggregate statistics, ranks drivers per fuel type, and selects the top-performing driver for each fuel type.

Go Solution

package main

func topDriverPerFuel() string {
    return `
    WITH DriverStats AS (
        SELECT
            v.fuel_type,
            d.driver_id,
            ROUND(AVG(t.rating), 2) AS rating,
            SUM(t.distance) AS distance,
            d.accidents
        FROM Drivers d
        JOIN Vehicles v ON d.driver_id = v.driver_id
        JOIN Trips t ON v.vehicle_id = t.vehicle_id
        GROUP BY v.fuel_type, d.driver_id, d.accidents
    ),
    RankedDrivers AS (
        SELECT
            fuel_type,
            driver_id,
            rating,
            distance,
            ROW_NUMBER() OVER (
                PARTITION BY fuel_type
                ORDER BY rating DESC, distance DESC, accidents ASC
            ) AS rn
        FROM DriverStats
    )
    SELECT
        fuel_type,
        driver_id,
        rating,
        distance
    FROM RankedDrivers
    WHERE rn = 1
    ORDER BY fuel_type ASC;
    `
}

The Go implementation mirrors the Python solution, returning the SQL query as a string. Go does not execute the SQL directly on LeetCode, so it simply returns the query.

Worked Examples

Using the example in the problem statement:

Join Drivers, Vehicles, Trips:

driver_id	name	accidents	vehicle_id	fuel_type	trip_id	distance	rating
1	Alice	1	100	Gasoline	201	50	5
1	Alice	1	100	Gasoline	202	30	4
2	Bob	3	101	Electric	203	100	4
2	Bob	3	101	Electric	204	80	5
3	Charlie	0	102	Gasoline	205	40	5
3	Charlie	0	102	Gasoline	206	60	5

Compute average rating and total distance per driver per fuel type:

fuel_type	driver_id	rating	distance	accidents
Gasoline	1	4.50	80	1
Gasoline	3	5.00	100	0
Electric	2	4.50	180	3

Rank within fuel type:

fuel_type	driver_id	rating	distance	rn
Gasoline	3	5.00	100	1
Gasoline	1	4.50	80	2
Electric	2	4.50	180	1

Select rn = 1 and order by fuel_type:

fuel_type	driver_id	rating	distance
Electric	2	4.50	180
Gasoline	3	5.00	100

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Each table is scanned once for join and aggregation; window function operates per fuel type.
Space	O(N)	Space required to store aggregated statistics per driver per fuel type.

The algorithm is efficient because it avoids repeated sorts by leveraging the ROW_NUMBER() window function.

Test Cases

# Basic provided example
assert Solution().topDriverPerFuel()  # returns the SQL query

# Edge case: one driver, multiple fuel types
# Edge case: multiple drivers with same rating and distance, verify accidents break tie
# Edge case: driver with no trips should not appear

Test	Why
Provided example	Validates normal case with multiple drivers and fuel types
One driver, multiple fuel types	Checks aggregation per fuel type works
Tie in rating and distance	Ensures accidents are used as tie-breaker
Driver with no trips	Ensures only drivers with trips are considered

Edge Cases

Drivers with no trips: