3601. Find Drivers with Improved Fuel Efficiency - Solution

The problem

Table: drivers

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| driver_id   | int     |
| driver_name | varchar |
+-------------+---------+
driver_id is the unique identifier for this table.
Each row contains information about a driver.

Table: trips

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| trip_id       | int     |
| driver_id     | int     |
| trip_date     | date    |
| distance_km   | decimal |
| fuel_consumed | decimal |
+---------------+---------+
trip_id is the unique identifier for this table.
Each row represents a trip made by a driver, including the distance traveled and fuel consumed for that trip.

Write a solution to find drivers whose fuel efficiency has improved by comparing their average fuel efficiency in the first half of the year with the second half of the year.

Calculate fuel efficiency as distance_km / fuel_consumed for each trip
First half: January to June, Second half: July to December
Only include drivers who have trips in both halves of the year
Calculate the efficiency improvement as (second_half_avg - first_half_avg)
Round all results to 2 decimal places

Return the result table ordered by efficiency improvement in descending order, then by driver name in ascending order.

The result format is in the following example.

Example:

Input:

drivers table:

+-----------+---------------+
| driver_id | driver_name   |
+-----------+---------------+
| 1         | Alice Johnson |
| 2         | Bob Smith     |
| 3         | Carol Davis   |
| 4         | David Wilson  |
| 5         | Emma Brown    |
+-----------+---------------+

trips table:

+---------+-----------+------------+-------------+---------------+
| trip_id | driver_id | trip_date  | distance_km | fuel_consumed |
+---------+-----------+------------+-------------+---------------+
| 1       | 1         | 2023-02-15 | 120.5       | 10.2          |
| 2       | 1         | 2023-03-20 | 200.0       | 16.5          |
| 3       | 1         | 2023-08-10 | 150.0       | 11.0          |
| 4       | 1         | 2023-09-25 | 180.0       | 12.5          |
| 5       | 2         | 2023-01-10 | 100.0       | 9.0           |
| 6       | 2         | 2023-04-15 | 250.0       | 22.0          |
| 7       | 2         | 2023-10-05 | 200.0       | 15.0          |
| 8       | 3         | 2023-03-12 | 80.0        | 8.5           |
| 9       | 3         | 2023-05-18 | 90.0        | 9.2           |
| 10      | 4         | 2023-07-22 | 160.0       | 12.8          |
| 11      | 4         | 2023-11-30 | 140.0       | 11.0          |
| 12      | 5         | 2023-02-28 | 110.0       | 11.5          |
+---------+-----------+------------+-------------+---------------+

Output:

+-----------+---------------+------------------+-------------------+------------------------+
| driver_id | driver_name   | first_half_avg   | second_half_avg   | efficiency_improvement |
+-----------+---------------+------------------+-------------------+------------------------+
| 2         | Bob Smith     | 11.24            | 13.33             | 2.10                   |
| 1         | Alice Johnson | 11.97            | 14.02             | 2.05                   |
+-----------+---------------+------------------+-------------------+------------------------+

Explanation:

Alice Johnson (driver_id = 1):
- First half trips (Jan-Jun): Feb 15 (120.5/10.2 = 11.81), Mar 20 (200.0/16.5 = 12.12)
- First half average efficiency: (11.81 + 12.12) / 2 = 11.97
- Second half trips (Jul-Dec): Aug 10 (150.0/11.0 = 13.64), Sep 25 (180.0/12.5 = 14.40)
- Second half average efficiency: (13.64 + 14.40) / 2 = 14.02
- Efficiency improvement: 14.02 - 11.97 = 2.05
Bob Smith (driver_id = 2):
- First half trips: Jan 10 (100.0/9.0 = 11.11), Apr 15 (250.0/22.0 = 11.36)
- First half average efficiency: (11.11 + 11.36) / 2 = 11.24
- Second half trips: Oct 5 (200.0/15.0 = 13.33)
- Second half average efficiency: 13.33
- Efficiency improvement: 13.33 - 11.24 = 2.10 (rounded to 2 decimal places)
Drivers not included:
- Carol Davis (driver_id = 3): Only has trips in first half (Mar, May)
- David Wilson (driver_id = 4): Only has trips in second half (Jul, Nov)
- Emma Brown (driver_id = 5): Only has trips in first half (Feb)

The output table is ordered by efficiency improvement in descending order then by name in ascending order.

Approach overview

Problem Overview: You have driver and trip records with distance and fuel data. For each driver, compare fuel efficiency in an earlier period against a later period, then return the drivers whose efficiency improved, with their names and the size of the improvement.

Approach 1: Correlated Subqueries (O(D × T) time, O(D) space)

For each driver row in the Drivers table, run two subqueries against Trips: one that computes efficiency (total distance divided by total fuel) for the early period, and one for the late period. Filter on the difference being positive. The logic is easy to verify because each subquery maps directly to one sentence of the requirement. The cost is that the Trips table gets scanned twice per driver, so the work grows with drivers times trips. Use this only as a correctness baseline on small tables.

Approach 2: Group Aggregation with Conditional SUM + JOIN (O(T + D) time, O(D) space)

Scan Trips once and group by driver_id. Inside each group, use SUM(CASE WHEN ... THEN distance END) and SUM(CASE WHEN ... THEN fuel END) to split the totals by period in a single pass. Compute efficiency as the ratio of these sums for each period. Then JOIN the grouped result back to the Drivers table to pull in driver names, and keep rows where the later efficiency is greater than the earlier one. The key insight is that a conditional sum replaces two subqueries, so each trip is read exactly once. Guard against divide-by-zero with NULLIF or by filtering drivers who have no fuel in a period. Use this approach in production queries and whenever the table is large.

Recommended for interviews: Interviewers expect the group aggregation with a join. Writing the correlated subquery shows you understand the requirement, but the single-pass conditional aggregation shows you can reason about query cost and avoid redundant table scans. Mention the ratio-of-sums versus average-of-ratios distinction out loud. Summing distance and fuel before dividing gives a weighted efficiency that matches the problem's intent, while averaging per-trip ratios can skew results when trip sizes vary.

Related reading: database problems, SQL joins, and aggregation queries.

Solution

Thinking

Scanning each driver's trips and splitting halves by hand easily drops drivers who lack a half-year and confuses a ratio of totals with a mean of per-trip efficiencies. The comparison is between the two half-year averages of the same driver.

Record distance/fuel per trip, then average by driver_id and half-year. After a pivot, drop rows missing a half and keep those whose second-half mean is strictly larger.

Join drivers for names and sort by improvement descending, then name ascending. Grouping and pivoting turn the half-year into an explicit aggregation key.

First, we perform group aggregation on the trips table to calculate the average fuel efficiency for each driver in the first half and the second half of the year.

Then, we join the results with the drivers table, filter out the drivers whose fuel efficiency has improved, and calculate the amount of improvement.

MySQL

# Write your MySQL query statement below
WITH
    T AS (
        SELECT
            driver_id,
            AVG(distance_km / fuel_consumed) half_avg,
            CASE
                WHEN MONTH(trip_date) <= 6 THEN 1
                ELSE 2
            END half
        FROM trips
        GROUP BY driver_id, half
    )
SELECT
    t1.driver_id,
    d.driver_name,
    ROUND(t1.half_avg, 2) first_half_avg,
    ROUND(t2.half_avg, 2) second_half_avg,
    ROUND(t2.half_avg - t1.half_avg, 2) efficiency_improvement
FROM
    T t1
    JOIN T t2 ON t1.driver_id = t2.driver_id AND t1.half < t2.half AND t1.half_avg < t2.half_avg
    JOIN drivers d ON t1.driver_id = d.driver_id
ORDER BY efficiency_improvement DESC, d.driver_name;

Pandas

import pandas as pd


def find_improved_efficiency_drivers(
    drivers: pd.DataFrame, trips: pd.DataFrame
) -> pd.DataFrame:
    trips = trips.copy()
    trips["trip_date"] = pd.to_datetime(trips["trip_date"])
    trips["half"] = trips["trip_date"].dt.month.apply(lambda m: 1 if m <= 6 else 2)
    trips["efficiency"] = trips["distance_km"] / trips["fuel_consumed"]
    half_avg = (
        trips.groupby(["driver_id", "half"])["efficiency"]
        .mean()
        .reset_index(name="half_avg")
    )
    pivot = half_avg.pivot(index="driver_id", columns="half", values="half_avg").rename(
        columns={1: "first_half_avg", 2: "second_half_avg"}
    )
    pivot = pivot.dropna()
    pivot = pivot[pivot["second_half_avg"] > pivot["first_half_avg"]]
    pivot["efficiency_improvement"] = (
        pivot["second_half_avg"] - pivot["first_half_avg"]
    ).round(2)
    pivot["first_half_avg"] = pivot["first_half_avg"].round(2)
    pivot["second_half_avg"] = pivot["second_half_avg"].round(2)
    result = pivot.reset_index().merge(drivers, on="driver_id")
    result = result.sort_values(
        by=["efficiency_improvement", "driver_name"], ascending=[False, True]
    )
    return result[
        [
            "driver_id",
            "driver_name",
            "first_half_avg",
            "second_half_avg",
            "efficiency_improvement",
        ]
    ]

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Correlated Subqueries	O(D × T)	O(D)	Small tables, easy correctness check
Group Aggregation + JOIN	O(T + D)	O(D)	General case, large trip logs, production queries

Frequently asked questions

Is Find Drivers with Improved Fuel Efficiency easy or hard?

It is rated Medium with a 49.2% acceptance rate. The difficulty comes from splitting one aggregation into period-specific sums and avoiding divide-by-zero errors, not from the join itself.

How to solve Find Drivers with Improved Fuel Efficiency in O(n)?

Group the Trips table by driver_id and use SUM(CASE WHEN ...) to split distance and fuel into the two time periods within each group. Divide the summed distance by the summed fuel for each period, then join to Drivers and filter where the later efficiency exceeds the earlier one.

Find Drivers with Improved Fuel Efficiency Python or Java solution?

This is a SQL problem, so the solution is written as a query, not in Python or Java. The same logic works in Pandas by grouping trips by driver, computing period sums with boolean masks, and merging with the drivers DataFrame.

What is the best approach for Find Drivers with Improved Fuel Efficiency?

The best approach is group aggregation with conditional SUM expressions, joined back to the Drivers table. It reads the Trips table once, computes both period efficiencies per driver in a single pass, and runs in O(T + D) time.

What data structure is used in Find Drivers with Improved Fuel Efficiency?

The problem uses relational tables rather than a classic data structure. The core operations are GROUP BY aggregation, conditional SUM expressions, and an INNER JOIN between the grouped results and the Drivers table.

What is the time complexity of Find Drivers with Improved Fuel Efficiency?

The optimal solution runs in O(T + D) time, where T is the number of trip rows and D is the number of drivers. The naive correlated subquery approach runs in O(D × T) because it rescans trips for every driver.

Is Find Drivers with Improved Fuel Efficiency asked at Google, Amazon, or Meta?

This is a database problem on LeetCode and is typically seen in SQL screening rounds rather than onsite algorithm rounds. Company-specific frequency varies by year, so check recent interview reports on LeetCode's company tags for current data.

Find Drivers with Improved Fuel Efficiency solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Find Drivers with Improved Fuel Efficiency solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems