Tejav
#3601

Find Drivers with Improved Fuel Efficiency

Medium
DatabaseHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

Aggregate trips by driver and calculate average fuel efficiency in one pass, then compare results. This reduces redundant calculations.

⚙️

Algorithm

3 steps
  1. 1Step 1: Aggregate trips by driver, calculating total distance and fuel consumed for both halves of the year.
  2. 2Step 2: Compute average fuel efficiency for each driver in both halves.
  3. 3Step 3: Filter drivers whose second half efficiency is greater than the first half.
solution.py1 lines
1SELECT driver_id, driver_name FROM (SELECT d.driver_id, d.driver_name, SUM(CASE WHEN trip_date BETWEEN '2023-01-01' AND '2023-06-30' THEN distance_km END) / SUM(CASE WHEN trip_date BETWEEN '2023-01-01' AND '2023-06-30' THEN fuel_consumed END) AS first_half_eff, SUM(CASE WHEN trip_date BETWEEN '2023-07-01' AND '2023-12-31' THEN distance_km END) / SUM(CASE WHEN trip_date BETWEEN '2023-07-01' AND '2023-12-31' THEN fuel_consumed END) AS second_half_eff FROM drivers d JOIN trips t ON d.driver_id = t.driver_id GROUP BY d.driver_id) AS efficiencies WHERE second_half_eff > first_half_eff;
ℹ

Complexity note: Single pass aggregation leads to linear complexity, storing results for each driver.

  • 1Efficiency is calculated as distance per fuel consumed.
  • 2Aggregating data reduces redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.