{x}
blog image

Top Travellers

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.

Solution Explanation:

This problem requires retrieving the total distance traveled by each user from two tables: Users and Rides. The solution uses a LEFT JOIN to combine the data and GROUP BY to aggregate the distances for each user. Let's break down the approach and code.

Approach:

  1. LEFT JOIN: A LEFT JOIN is used to combine the Users and Rides tables. This ensures that all users are included in the result, even if they haven't made any rides. If a user has rides, their corresponding distances are joined; otherwise, the Rides columns will have NULL values. The join condition is u.id = r.user_id, matching user IDs from both tables.

  2. GROUP BY u.id: After the join, the result set contains all users and their associated rides. The GROUP BY u.id clause groups the rows based on user ID. This allows us to aggregate the distance values for each user.

  3. SUM(distance): The SUM(distance) function calculates the total distance for each group (each user).

  4. IFNULL(SUM(distance), 0): This handles users who have no rides. If SUM(distance) is NULL (meaning no rides), it replaces it with 0. This ensures every user has a travelled_distance value.

  5. ORDER BY 2 DESC, 1 ASC: Finally, the results are ordered. ORDER BY 2 DESC sorts the users in descending order of their travelled_distance (the second column in the output). If two users have the same distance, ORDER BY 1 ASC sorts them in ascending order of their name (the first column).

MySQL Code:

SELECT name, IFNULL(SUM(distance), 0) AS travelled_distance
FROM
    Users AS u
    LEFT JOIN Rides AS r ON u.id = r.user_id
GROUP BY u.id
ORDER BY 2 DESC, 1;

Time and Space Complexity Analysis:

  • Time Complexity: The time complexity is dominated by the GROUP BY operation, which generally takes O(N log N) or O(N) time depending on the database system's optimization. N is the number of rows in the joined table (which is at most the sum of the number of rows in Users and Rides). The sorting operation (ORDER BY) also contributes to this complexity.

  • Space Complexity: The space complexity is determined by the size of the intermediate result set after the LEFT JOIN and before the GROUP BY operation. In the worst case, this is proportional to the size of the joined table, which is at most O(M*N), where M is the number of users and N is the maximum number of rides per user. However, in practice, the database system often optimizes this process, and the actual space usage might be much lower. The final output space complexity is O(M), where M is the number of users.

This solution efficiently combines data from two tables, aggregates the results, and provides the desired output, meeting the requirements of the problem. The use of LEFT JOIN and IFNULL ensures that all users are included in the output, regardless of whether they have any rides.