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.
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.
MySQL
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.
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.
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.
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.
MySQL
| Approach | Complexity |
|---|---|
| SQL Join and Aggregation | Time Complexity: O(n log n), where n is the number of rides due to aggregation and sorting |
| Using Data Structures for Aggregation | Time Complexity: O(n log n) due to sorting operation, where n is the number of users + rides. |
| LEFT JOIN + GROUP BY | — |
| 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 |
LeetCode 1407 Interview SQL Question with Detailed Explanation | Practice SQL • Everyday Data Science • 7,772 views views
Watch 9 more video solutions →Practice Top Travellers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor