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.
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.
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.
C
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.
| 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. |
LeetCode 1407 Interview SQL Question with Detailed Explanation | Practice SQL • Everyday Data Science • 6,109 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