Domain 1EasyCORE

Top Travellers

The problem "Top Travellers" requires us to determine the total distance traveled by each user from a given table of trips. The input consists of two tables: `Users` and `Trips`. The `Users` table contains user IDs and names, while the `Trips` table contains trip IDs, user IDs, and distances traveled for each trip. The output should be a list of users sorted by their total distance traveled in descending order.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

1407. Top Travellers

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 84.0%


Problem Breakdown

The problem “Top Travellers” requires us to determine the total distance traveled by each user from a given table of trips. The input consists of two tables: Users and Trips. The Users table contains user IDs and names, while the Trips table contains trip IDs, user IDs, and distances traveled for each trip. The output should be a list of users sorted by their total distance traveled in descending order.

Inputs:

  • Users: A table with columns id (user ID) and name (user name).
  • Trips: A table with columns id (trip ID), user_id (user ID), and distance (distance traveled).

Outputs:

  • A list of users sorted by their total distance traveled in descending order, along with the total distance.

Implicit Constraints/Edge Cases:

  • The Trips table might be empty.
  • Users might not have any trips recorded.
  • Duplicate entries in the Trips table should be considered only once for each user.

Intuition

A brute-force approach would involve iterating over each user, summing up their distances from the Trips table, and then sorting the results. However, this approach is inefficient with a time complexity of O(n^2) due to nested loops (one for users and one for trips).

The key insight is to leverage SQL aggregation functions to efficiently compute the total distance traveled by each user in a single pass through the data. This reduces the time complexity to O(n), where n is the number of trips.

Approach

  1. Join Tables: Perform an inner join between the Users and Trips tables on the user_id column to associate each trip with its corresponding user.
  2. Aggregate Data: Use the GROUP BY clause to group the results by user ID, allowing us to sum up the distances for each user.
  3. Sort Results: Order the aggregated results by the total distance in descending order using the ORDER BY clause.
  4. Select Columns: Select only the required columns (name and the summed distance) for the final output.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of trips. The SQL query efficiently processes each trip once.
  • Space Complexity: O(m), where m is the number of unique users, as we store the aggregated results for each user.

Solution

import pandas as pd

def top_travellers(users: pd.DataFrame, trips: pd.DataFrame) -> pd.DataFrame:
    # Join Users and Trips tables on user_id
    merged_df = pd.merge(users, trips, left_on='id', right_on='user_id', how='left')
    
    # Group by user_id and sum the distances
    aggregated_df = merged_df.groupby('name')['distance'].sum().reset_index()
    
    # Rename columns for clarity
    aggregated_df.columns = ['name', 'total_distance']
    
    # Sort by total distance in descending order
    sorted_df = aggregated_df.sort_values(by='total_distance', ascending=False)
    
    return sorted_df

Edge Cases Handled

  • Empty Trips Table: If the Trips table is empty, the result will be an empty DataFrame since no distances are summed.
  • Users with No Trips: Users without any trips will not appear in the final output as they have a sum of zero distance.
  • Duplicate Entries: The use of GROUP BY ensures that duplicate entries for the same user and trip are considered only once.