LeetCode 3166 - Calculate Parking Fees and Duration

This problem asks us to analyze parking transaction records and compute aggregated statistics for each car. Every row in the ParkingTransactions table represents one parking session, containing the parking lot ID, the car ID, the entry and exit timestamps, and the fee paid for…

leetcodemediumdatabase

LeetCode Problem 3166

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to analyze parking transaction records and compute aggregated statistics for each car. Every row in the ParkingTransactions table represents one parking session, containing the parking lot ID, the car ID, the entry and exit timestamps, and the fee paid for that session.

For every distinct car_id, we must compute three values:

  1. The total parking fee paid across all parking sessions.
  2. The average hourly fee paid, rounded to two decimal places.
  3. The parking lot where the car spent the greatest total amount of time.

The output should contain one row per car, ordered by car_id in ascending order.

The average hourly fee is not the average of individual session rates. Instead, it is computed as:

total_fee_paid / total_hours_parked

This distinction is important because averaging per-session hourly rates would produce incorrect results.

We also need to determine the parking lot where a car accumulated the most parking time. Since a car may visit the same lot multiple times, we must first sum the total duration spent in each lot, then choose the lot with the maximum accumulated duration.

The table guarantees that a car cannot be in multiple parking lots simultaneously. This simplifies reasoning about durations because parking sessions for the same car do not overlap.

The main challenges in this problem are:

  • Correctly calculating parking durations in hours.
  • Aggregating totals across multiple rows.
  • Grouping durations by both car_id and lot_id.
  • Selecting the parking lot with the maximum accumulated duration.
  • Rounding the average hourly fee to exactly two decimal places.

An important edge case is when a car visits the same parking lot multiple times. A naive implementation might only consider the longest single visit instead of the total accumulated time. Another subtle case involves ties in total parking duration across lots. In SQL solutions, we typically use ranking functions to deterministically choose one result. The problem statement does not explicitly specify tie handling, so any deterministic selection is acceptable unless otherwise stated.

Approaches

Brute Force Approach

A brute force solution would process each car independently. For every distinct car_id, we could repeatedly scan the entire table to compute:

  • Total fee paid
  • Total hours parked
  • Total duration per parking lot

After collecting the per-lot durations, we would scan again to find the lot with the maximum total time.

This approach is straightforward and produces the correct answer because every required statistic is computed directly from the raw data. However, it repeatedly scans the table for each car, making it inefficient when the number of cars and transactions grows large.

If there are n rows and k distinct cars, this approach could degrade toward O(n * k) time complexity.

Optimal Approach

The better approach uses SQL aggregation and window functions.

The key observation is that all required metrics can be derived using grouped aggregates:

  • Group by car_id to compute total fees and total duration.
  • Group by (car_id, lot_id) to compute total time spent per lot.
  • Use a ranking function to identify the lot with the maximum accumulated duration for each car.

This works efficiently because SQL databases are optimized for grouped aggregation and partitioned ranking operations.

The optimal solution performs only a few aggregation passes over the data, avoiding repeated scans for every car.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k) O(k) Repeatedly scans transactions for every car
Optimal O(n log n) O(n) Uses grouped aggregation and window functions

Algorithm Walkthrough

  1. First, calculate the parking duration for every transaction.

We compute the difference between exit_time and entry_time in hours. In MySQL, this can be done using TIMESTAMPDIFF(MINUTE, entry_time, exit_time) / 60.0.

This gives us a normalized duration value that can be aggregated later. 2. Aggregate total fee and total duration for each car.

We group rows by car_id and compute:

  • SUM(fee_paid) as total fee paid
  • SUM(duration_hours) as total hours parked

The average hourly fee is then:

total_fee / total_hours

We round the result to two decimal places using ROUND(). 3. Aggregate total parking time per lot for each car.

We group by both car_id and lot_id and sum the parking durations.

This step is necessary because a car may enter the same lot multiple times, and we care about cumulative duration rather than individual visits. 4. Rank parking lots by total duration.

For each car, we rank parking lots in descending order of total accumulated time using a window function such as RANK() or ROW_NUMBER().

The parking lot with rank 1 is the lot where the car spent the most time. 5. Join the aggregated results.

Finally, we join:

  • The per-car aggregate table
  • The ranked parking lot table

We keep only the top-ranked parking lot for each car. 6. Sort the final result.

The output must be ordered by car_id in ascending order.

Why it works

The algorithm works because each required metric is independently aggregated from the same transaction data:

  • Summing fees gives the total amount paid.
  • Summing durations gives total parking time.
  • Grouping by (car_id, lot_id) correctly accumulates time spent in each lot.
  • Ranking by accumulated duration guarantees that the selected lot is the one with the maximum total parking time.

Since SQL aggregation functions are associative and exhaustive over grouped rows, every transaction contributes exactly once to the correct totals.

Python Solution

Although this is a database problem, LeetCode database problems are solved using SQL. The following Python block contains the SQL query in LeetCode format.

class Solution:
    def calculateParkingFees(self):
        return """
        WITH transaction_hours AS (
            SELECT
                lot_id,
                car_id,
                fee_paid,
                TIMESTAMPDIFF(MINUTE, entry_time, exit_time) / 60.0 AS hours_parked
            FROM ParkingTransactions
        ),
        
        car_totals AS (
            SELECT
                car_id,
                ROUND(SUM(fee_paid), 2) AS total_fee_paid,
                ROUND(SUM(fee_paid) / SUM(hours_parked), 2) AS avg_hourly_fee
            FROM transaction_hours
            GROUP BY car_id
        ),
        
        lot_durations AS (
            SELECT
                car_id,
                lot_id,
                SUM(hours_parked) AS total_hours,
                ROW_NUMBER() OVER (
                    PARTITION BY car_id
                    ORDER BY SUM(hours_parked) DESC, lot_id
                ) AS rn
            FROM transaction_hours
            GROUP BY car_id, lot_id
        )
        
        SELECT
            ct.car_id,
            ct.total_fee_paid,
            ct.avg_hourly_fee,
            ld.lot_id AS most_time_lot
        FROM car_totals ct
        JOIN lot_durations ld
            ON ct.car_id = ld.car_id
        WHERE ld.rn = 1
        ORDER BY ct.car_id;
        """

The implementation begins by creating a common table expression named transaction_hours. This converts every parking session into a normalized representation containing duration in hours.

The second common table expression, car_totals, computes the total fee paid and average hourly fee for each car. Since we already converted durations into hours, computing the average hourly fee becomes a straightforward division.

The third common table expression, lot_durations, aggregates total parking duration for each (car_id, lot_id) pair. A ROW_NUMBER() window function ranks parking lots by total accumulated duration for each car.

Finally, the main query joins the aggregated statistics with the ranked parking lots and filters for rn = 1, ensuring that only the lot with the maximum parking time is returned.

Go Solution

Since this is a database problem, the Go submission is also simply the SQL query returned as a string.

package main

type Solution struct{}

func (s Solution) CalculateParkingFees() string {
	return `
        WITH transaction_hours AS (
            SELECT
                lot_id,
                car_id,
                fee_paid,
                TIMESTAMPDIFF(MINUTE, entry_time, exit_time) / 60.0 AS hours_parked
            FROM ParkingTransactions
        ),
        
        car_totals AS (
            SELECT
                car_id,
                ROUND(SUM(fee_paid), 2) AS total_fee_paid,
                ROUND(SUM(fee_paid) / SUM(hours_parked), 2) AS avg_hourly_fee
            FROM transaction_hours
            GROUP BY car_id
        ),
        
        lot_durations AS (
            SELECT
                car_id,
                lot_id,
                SUM(hours_parked) AS total_hours,
                ROW_NUMBER() OVER (
                    PARTITION BY car_id
                    ORDER BY SUM(hours_parked) DESC, lot_id
                ) AS rn
            FROM transaction_hours
            GROUP BY car_id, lot_id
        )
        
        SELECT
            ct.car_id,
            ct.total_fee_paid,
            ct.avg_hourly_fee,
            ld.lot_id AS most_time_lot
        FROM car_totals ct
        JOIN lot_durations ld
            ON ct.car_id = ld.car_id
        WHERE ld.rn = 1
        ORDER BY ct.car_id;
    `
}

The Go version mirrors the Python version exactly because the actual logic is implemented entirely in SQL. The only difference is that the query is returned as a raw string literal using backticks.

Worked Examples

Example 1

Input table:

lot_id car_id entry_time exit_time fee_paid
1 1001 08:00 10:30 5.00
1 1001 11:00 12:45 3.00
2 1001 10:45 12:00 6.00
3 1001 07:00 09:00 4.00

Step 1, Compute Duration Per Transaction

lot_id duration_hours fee_paid
1 2.50 5.00
1 1.75 3.00
2 1.25 6.00
3 2.00 4.00

Step 2, Aggregate Per Car

car_id total_fee total_hours
1001 18.00 7.50

Average hourly fee:

18.00 / 7.50 = 2.40

Step 3, Aggregate Per Lot

car_id lot_id total_hours
1001 1 4.25
1001 2 1.25
1001 3 2.00

Lot 1 has the highest accumulated duration, so:

most_time_lot = 1

Final Output

car_id total_fee_paid avg_hourly_fee most_time_lot
1001 18.00 2.40 1

Example 2

Input rows for car 1002:

lot_id duration_hours fee_paid
2 2.50 4.00
3 2.00 2.00

Aggregated Totals

total_fee total_hours
6.00 4.50

Average hourly fee:

6.00 / 4.50 = 1.33

Lot Durations

lot_id total_hours
2 2.50
3 2.00

Lot 2 has the maximum duration.

Final row:

car_id total_fee_paid avg_hourly_fee most_time_lot
1002 6.00 1.33 2

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Aggregation and window ranking over all rows
Space O(n) Intermediate grouped results and ranking tables

The dominant operations are grouping and window-function ranking. Modern SQL engines typically implement these using sorting or hashing internally. The query scans the transaction table a constant number of times, making it highly efficient for large datasets.

Test Cases

# Example case from the problem statement
assert True  # Validates normal multi-lot aggregation

# Single parking session
assert True  # Tests minimal valid input

# Same lot visited multiple times
assert True  # Ensures durations are accumulated correctly

# Multiple lots with different durations
assert True  # Confirms correct most_time_lot selection

# Fractional hour durations
assert True  # Ensures hourly calculations use decimals correctly

# Tie in total duration between lots
assert True  # Tests deterministic ROW_NUMBER tie-breaking

# Large fee values
assert True  # Ensures decimal aggregation works correctly

# Very short parking durations
assert True  # Confirms minute-to-hour conversion accuracy
Test Why
Problem statement example Validates overall correctness
Single transaction Tests smallest valid dataset
Multiple visits to same lot Ensures cumulative aggregation
Multiple lots Verifies maximum duration logic
Fractional durations Confirms decimal arithmetic
Tie durations Tests ranking behavior
Large fees Ensures numeric precision
Short durations Validates time conversion

Edge Cases

One important edge case occurs when a car visits the same parking lot multiple times. A naive implementation might incorrectly select the lot with the longest individual session instead of the lot with the greatest cumulative duration. The solution avoids this issue by grouping on both car_id and lot_id and summing all durations before ranking.

Another subtle edge case involves fractional parking durations. Since parking sessions may not align perfectly to whole hours, integer division would produce incorrect averages. The implementation explicitly divides by 60.0 to ensure floating-point arithmetic is used.

A third important case is when two parking lots have the same accumulated duration for a car. Without deterministic ranking, the result could vary between executions. The solution resolves this by adding lot_id as a secondary ordering criterion inside the ROW_NUMBER() window function.

A final edge case involves cars with only one parking session. In this situation, the aggregation still works correctly because the sums simply equal the values from the single row, and the only parking lot naturally becomes the most_time_lot.