Watch 10 video solutions for Top Travellers, a easy level problem involving Database. This walkthrough by Everyday Data Science has 7,772 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 | Time | Space | When to Use |
|---|---|---|---|
| SQL Join and Aggregation | O(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 |
