1407. Top Travellers - Solution & Explanation

The problem

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.

Approach overview

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 1: SQL Join and Aggregation

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.

MySQL

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;

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.

Complexity

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.

Try this approach in the editor

Approach 2: Using Data Structures for Aggregation

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.

Python

users = {1: 'Alice', 2: 'Bob', 3: 'Alex', 4: 'Donald', 7: 'Lee', 13: 'Jonathan', 19: 'Elvis'}
rides = [(1, 120), (2, 317), (3, 222), (7, 100), (13, 312), (19, 50), (7, 120), (19, 400), (7, 230)]
from collections import defaultdict
travelled = defaultdict(int)
for user_id, distance in rides:
    travelled[user_id] += distance

result = [(users[id], travelled.get(id, 0)) for id in users]
result.sort(key=lambda x: (-x[1], x[0]))

for name, distance in result:
    print(name, distance)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct {
    int id;
    char name[20];
} User;

typedef struct {
    int user_id;
    int distance;
} Ride;

typedef struct {
    char name[20];
    int distance;
} Result;

int compare(const void *a, const void *b) {
    Result *ra = (Result *)a;
    Result *rb = (Result *)b;
    if (rb->distance != ra->distance)
        return rb->distance - ra->distance;
    return strcmp(ra->name, rb->name);
}

int main() {
    User users[] = {{1, "Alice"}, {2, "Bob"}, {3, "Alex"}, {4, "Donald"}, {7, "Lee"}, {13, "Jonathan"}, {19, "Elvis"}};
    Ride rides[] = {{1, 120}, {2, 317}, {3, 222}, {7, 100}, {13, 312}, {19, 50}, {7, 120}, {19, 400}, {7, 230}};
    int n_users = sizeof(users) / sizeof(users[0]);
    int n_rides = sizeof(rides) / sizeof(rides[0]);
    
    Result results[n_users];
    memset(results, 0, sizeof(results));
    for (int i = 0; i < n_users; i++) {
        strcpy(results[i].name, users[i].name);
    }

    for (int i = 0; i < n_rides; i++) {
        int user_id = rides[i].user_id;
        for (int j = 0; j < n_users; j++) {
            if (user_id == users[j].id) {
                results[j].distance += rides[i].distance;
                break;
            }
        }
    }

    qsort(results, n_users, sizeof(Result), compare);

    for (int i = 0; i < n_users; i++) {
        printf("%s %d\n", results[i].name, results[i].distance);
    }

    return 0;
}

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.

Complexity

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.

Try this approach in the editor

Complexity comparison

Approach	Complexity
SQL Join and Aggregation	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.
Using Data Structures for Aggregation	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.

Complexity analysis

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

Top Travellers solution and explanation

The problem

Approach overview

Approach 1: SQL Join and Aggregation

Approach 2: Using Data Structures for Aggregation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Top Travellers solution and explanation

The problem

Approach overview

Approach 1: SQL Join and Aggregation

Approach 2: Using Data Structures for Aggregation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems