Top Travellers

Difficulty: Easy | Acceptance: 57.30% | Paid: No Topics: Database

Table: Users +--------------+---------+ | Column Name | Type | +--------------+---------+ | id | int | | name | varchar | +--------------+---------+ id is the primary key (column with unique values) for this table. name is the name of the user.

Table: Rides +--------------+---------+ | Column Name | Type | +--------------+---------+ | ride_id | int | | user_id | int | | distance | int | +--------------+---------+ ride_id is the primary key (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, and 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.

• Examples
• Constraints
• Approach 1: Left Join with Aggregation
• Approach 2: Pre-aggregation then Join

Examples

Example 1

Input: Users table: +------+-----------+ | id | name | +------+-----------+ | 1 | Alice | | 2 | Bob | | 3 | Alex | | 4 | Donald | | 7 | Lee | | 13 | Jonathan | | 19 | Elvis | +------+-----------+ Rides table: +------+----------+----------+ | ride_id | user_id | distance | +------+----------+----------+ | 1 | 1 | 120 | | 2 | 2 | 317 | | 3 | 3 | 222 | | 4 | 7 | 100 | | 5 | 13 | 40 | | 6 | 19 | 80 | | 7 | 7 | 60 | | 8 | 19 | 100 | | 9 | 7 | 90 | | 10 | 1 | 60 | +------+----------+----------+

Output: +----------+--------------------+ | name | travelled_distance | +----------+--------------------+ | Elvis | 180 | | Lee | 250 | | Bob | 317 | | Jonathan | 40 | | Alex | 222 | | Alice | 180 | | Donald | 0 | +----------+--------------------+

Explanation:

• Elvis and Alice traveled 180 units, Elvis is listed before Alice because “Elvis” < “Alice” in alphabetical order.
• Lee, Bob, Alex, and Jonathan traveled 250, 317, 222, and 40 units respectively.
• Donald traveled 0 units.

Constraints

0 <= Users.id <= 10⁵
0 <= Rides.ride_id <= 10⁵
0 <= Rides.distance <= 10⁵

Approach 1: Left Join with Aggregation

Intuition We need to combine the Users table with the Rides table. A LEFT JOIN ensures that users who have not taken any rides are still included in the result. We then group by the user and sum the distances, handling NULL values (which occur when a user has no rides) by converting them to 0.

Steps

• Perform a LEFT JOIN between Users and Rides on the user_id.
• Group the results by the user’s id and name.
• Use SUM() to calculate the total distance.
• Use COALESCE() (or IFNULL) to replace NULL sums with 0.
• Order the results by travelled_distance descending, then by name ascending.

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

Complexity

• Time: O(N + M log M) where N is the total number of rows in the joined table (or sum of rows in both tables for the algorithmic approach) and M is the number of unique users. Sorting dominates the complexity.
• Space: O(M) to store the aggregated distances for each user.
• Notes: The LEFT JOIN is crucial here; an INNER JOIN would exclude users with 0 distance.

Approach 2: Pre-aggregation then Join

Intuition Instead of joining the raw tables and then aggregating, we can first aggregate the Rides table to calculate the total distance per user. Then, we perform a LEFT JOIN of this aggregated result with the Users table. This can sometimes be more efficient as it reduces the number of rows involved in the join operation.

Steps

• Create a subquery (or CTE) that selects user_id and the sum of distance from the Rides table, grouping by user_id.
• Perform a LEFT JOIN of the Users table with this subquery on user_id.
• Use COALESCE on the summed distance to handle users with no rides.
• Order the final result by travelled_distance descending and name ascending.

SELECT u.name, COALESCE(r.total_distance, 0) AS travelled_distance
FROM Users u
LEFT JOIN (
    SELECT user_id, SUM(distance) AS total_distance
    FROM Rides
    GROUP BY user_id
) r ON u.id = r.user_id
ORDER BY travelled_distance DESC, u.name ASC

Complexity

• Time: O(N + M log M). We iterate through Rides once to aggregate (O(N)) and Users once to join (O(M)). Sorting takes O(M log M).
• Space: O(K) where K is the number of unique users in Rides (for the hash map) plus O(M) for the result list.
• Notes: This approach is logically equivalent to the first but can perform better on large datasets where the Rides table is significantly larger than the Users table, as the join operation works on fewer rows.