Skip to main content
Talentd

Top Travellers - Solution & Explanation

EasyDatabase7 min readAsked at: Google, Point72
Practice this problem

Problem Statement

Table: Users

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| name          | varchar |
+---------------+---------+
id is the column with unique values for this table.
name is the name of the user.

 

Table: Rides

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| user_id       | int     |
| distance      | int     |
+---------------+---------+
id is the column with unique values for this table.
user_id is the id of the user who traveled the distance "distance".

 

Write a solution to report the distance traveled by each user.

Return the result table ordered by travelled_distance in descending order, if two or more users traveled the same distance, order them by their name in ascending order.

The result format is in the following example.

 

Example 1:

Input: 
Users table:
+------+-----------+
| id   | name      |
+------+-----------+
| 1    | Alice     |
| 2    | Bob       |
| 3    | Alex      |
| 4    | Donald    |
| 7    | Lee       |
| 13   | Jonathan  |
| 19   | Elvis     |
+------+-----------+
Rides table:
+------+----------+----------+
| id   | user_id  | distance |
+------+----------+----------+
| 1    | 1        | 120      |
| 2    | 2        | 317      |
| 3    | 3        | 222      |
| 4    | 7        | 100      |
| 5    | 13       | 312      |
| 6    | 19       | 50       |
| 7    | 7        | 120      |
| 8    | 19       | 400      |
| 9    | 7        | 230      |
+------+----------+----------+
Output: 
+----------+--------------------+
| name     | travelled_distance |
+----------+--------------------+
| Elvis    | 450                |
| Lee      | 450                |
| Bob      | 317                |
| Jonathan | 312                |
| Alex     | 222                |
| Alice    | 120                |
| Donald   | 0                  |
+----------+--------------------+
Explanation: 
Elvis and Lee traveled 450 miles, Elvis is the top traveler as his name is alphabetically smaller than Lee.
Bob, Jonathan, Alex, and Alice have only one ride and we just order them by the total distances of the ride.
Donald did not have any rides, the distance traveled by him is 0.

Approach Overview

Problem Overview: You are given two tables: Users and Rides. Each ride records the distance traveled by a user. The task is to compute the total distance traveled by every user, including users who never took a ride, and return the result sorted by total distance (descending) and name (ascending).

Approach 1: SQL Join and Aggregation (O(U + R) time, O(U) space)

This approach relies on SQL aggregation. Perform a LEFT JOIN between the Users table and the Rides table using user_id. A left join ensures users without rides still appear in the result set. Use SUM(distance) to aggregate travel distance per user and wrap it with COALESCE (or IFNULL in MySQL) so users with no rides return 0. Finally, apply GROUP BY users.id and sort using ORDER BY travelled_distance DESC, name ASC. The database engine scans rides once and groups by user, giving linear complexity relative to the table sizes. This pattern is common in reporting queries and leaderboard-style problems involving SQL aggregation.

Approach 2: Using Data Structures for Aggregation (O(U + R) time, O(U) space)

If you were solving this outside SQL (for example in Python or C), the same logic can be implemented with a hash map. First iterate through the rides list and accumulate distances in a dictionary keyed by user_id. Each entry stores the running sum of travel distance. Next iterate through the users list, retrieve the aggregated distance from the map, and default to 0 when a user does not exist in the map. Store the results as pairs of (name, travelled_distance), then sort them by distance descending and name ascending. Hash map lookups make aggregation constant time, which keeps the total complexity linear. This mirrors how databases internally execute grouped aggregation using hash tables, making it a practical translation of a hash table approach to a database query problem.

Recommended for interviews: The SQL join and aggregation solution is the expected answer for database interviews. It demonstrates understanding of joins, grouping, and null handling. The data structure approach is useful when implementing the same logic in application code and shows that you understand the underlying aggregation process beyond SQL syntax.

Approach 1: SQL Join and Aggregation

The key to solving this problem is to join the Users and Rides tables on the user's ID, group the results by user, and compute the sum of the distances. Once the sum is calculated for each user, sort the results primarily by the total distance traveled in descending order and secondarily by the user's name in ascending order.

Use a LEFT JOIN to ensure that every user is included in the result, even users without rides. COALESCE is used to handle null sums for users without rides by replacing null with 0. Finally, the results are grouped by user name and ID, and results are sorted by the travelled distance from highest to lowest, with secondary sorting alphabetically by name.

Code

MySQL

MySQL

Complexity

Time Complexity: O(n log n), where n is the number of rides due to aggregation and sorting
Space Complexity: O(1), excluding the result space.

Try this approach in the editor →

Approach 2: Using Data Structures for Aggregation

Another approach involves using arrays, hashes, or dictionaries in high-level programming languages to manually join, group, and sort data. First, construct a mapping of users, then iterate over the ride data to accumulate distances for each user id. After summation, sort the data based on distance and name accordingly.

This code starts by mapping user IDs to names and using a defaultdict to accumulate the total distance for each user ID. It then constructs a list of tuples containing the user's name and their total distance. After the distances are summed, the results are sorted by total distance and then by user's name.

Code

PythonC

Python

C

Complexity

Time Complexity: O(n log n) due to sorting operation, where n is the number of users + rides.
Space Complexity: O(n) to store travelled distances and sorted result.

Try this approach in the editor →

Approach 3: LEFT JOIN + GROUP BY

We can use a left join to join the Users table with the Rides table on the condition of user id, and then group by user id to calculate the travel distance for each user. Note that if a user has no travel records, the travel distance is 0.

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
SQL Join and Aggregation

Time Complexity: O(n log n), where n is the number of rides due to aggregation and sorting
Space Complexity: O(1), excluding the result space.

Using Data Structures for Aggregation

Time Complexity: O(n log n) due to sorting operation, where n is the number of users + rides.
Space Complexity: O(n) to store travelled distances and sorted result.

LEFT JOIN + GROUP BY—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
SQL Join and AggregationO(U + R)O(U)Best for database queries where results must be computed directly from relational tables
Hash Map Aggregation (Python/C)O(U + R)O(U)Useful when processing ride data in application code instead of SQL

Video Solution

LeetCode 1407 Interview SQL Question with Detailed Explanation | Practice SQL • Everyday Data Science • 8,190 views views

Watch 9 more video solutions →

Frequently Asked Questions

Top Travellers Python solution
A Python solution iterates through rides, accumulating distances in a dictionary keyed by user_id. Then iterate through the users list, fetch the aggregated distance (default 0), store results as tuples, and sort by distance descending and name ascending. The approach runs in O(U + R) time.
Is Top Travellers easy or hard?
Top Travellers is classified as an Easy database problem. The challenge mainly tests understanding of SQL joins, GROUP BY aggregation, and handling users without matching rows using LEFT JOIN.
How to solve Top Travellers in O(n)?
Aggregate distances by user in a single pass through the rides data. In SQL this is done using SUM(distance) with GROUP BY after joining users and rides. In application code you can store totals in a hash map keyed by user_id, then iterate through users and sort the final results.
What is the best approach for Top Travellers?
The most efficient solution uses a SQL LEFT JOIN between the Users and Rides tables followed by GROUP BY aggregation. SUM(distance) calculates total travel distance per user while COALESCE or IFNULL converts null values to 0 for users without rides. The final result is sorted by travelled distance descending and name ascending.
Is Top Travellers asked at Google/Amazon/Meta?
Top Travellers represents a common database interview pattern involving joins and aggregation. Similar problems appear in SQL interview rounds at companies like Amazon, Google, and Meta where candidates must compute grouped statistics from relational tables.
What data structure is used in Top Travellers?
The core data structure concept is a hash map used for aggregation. In SQL this behavior is handled internally by the database engine during GROUP BY operations. In languages like Python or C, a dictionary or hash table stores total distance per user.
What is the time complexity of Top Travellers?
The typical SQL aggregation solution runs in O(U + R) time where U is the number of users and R is the number of rides. The database scans rides and groups them by user_id. Space complexity is O(U) to maintain aggregated totals per user.

Ready to solve this problem?

Practice Top Travellers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary