LeetCode Problem 1407

Difficulty: 🟢 Easy
Topics: Database

Solution

LeetCode 1407 - Top Travellers

Problem Understanding

This problem gives us two database tables, Users and Rides.

The Users table contains information about each user. Every user has a unique id and a corresponding name.

The Rides table contains ride records. Each ride has its own unique id, a user_id indicating which user took the ride, and a distance representing how far the ride traveled.

The goal is to calculate the total traveled distance for every user. This means we must sum all ride distances belonging to the same user.

There are several important details in the requirements:

1. Every user must appear in the final result, even if they never took a ride.
2. Users without rides should have a traveled distance of 0.
3. The result must be sorted by:

• travelled_distance in descending order
• name in ascending alphabetical order when distances are equal

Conceptually, this is a classic SQL aggregation problem involving:

• joining two tables
• grouping rides by user
• summing distances
• handling missing ride records
• sorting the final output

The input size is relatively small for this Easy-level problem, but the main challenge is understanding how SQL joins and aggregation interact.

A naive implementation can easily fail in a few ways:

• Using an INNER JOIN instead of a LEFT JOIN, which would exclude users with no rides.
• Forgetting to replace NULL sums with 0.
• Sorting only by distance and ignoring the secondary alphabetical ordering rule.
• Grouping incorrectly and producing duplicate users.

The problem guarantees that:

• Users.id is unique.
• Rides.id is unique.
• Rides.user_id references a valid user.

This means we do not need to worry about invalid foreign keys.

Approaches

Brute Force Approach

The brute-force approach would process each user independently.

For every user in the Users table:

1. Scan the entire Rides table.
2. Collect all rides belonging to that user.
3. Sum their distances.
4. Store the result.

After computing totals for every user, sort the final list according to the required ordering rules.

This approach is correct because every ride is checked against every user, guaranteeing that all relevant distances are included in the total.

However, this method is inefficient because the Rides table is scanned repeatedly. If there are U users and R rides, the total work becomes O(U × R).

Optimal Approach

The key observation is that we should aggregate ride distances only once.

Instead of repeatedly scanning the rides table, we can:

1. Group rides by user_id.
2. Compute the sum of distances for each user in a single pass.
3. Join the aggregated results with the Users table.

In SQL, this is naturally solved using:

• LEFT JOIN
• GROUP BY
• SUM
• COALESCE

The LEFT JOIN ensures that users without rides still appear.

The aggregation computes each user's total traveled distance exactly once, making the solution much more efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(U × R)	O(1) extra	Scans all rides for every user
Optimal	O(U + R)	O(U)	Aggregates rides once and joins efficiently

Algorithm Walkthrough

1. Start with the Users table because every user must appear in the output, including users without rides.
2. Perform a LEFT JOIN between Users and Rides using:

Users.id = Rides.user_id

A LEFT JOIN keeps all rows from Users, even when no matching ride exists. 3. Group the joined rows by:

Users.id, Users.name

Grouping allows us to aggregate all rides belonging to the same user. 4. Compute the total traveled distance using:

SUM(Rides.distance)

This adds together all distances for each user. 5. Users without rides will produce NULL from the SUM aggregation. Convert these values to 0 using:

COALESCE(SUM(Rides.distance), 0)

6. Rename the aggregated column as:

travelled_distance

7. Sort the final result:

• first by travelled_distance DESC
• then by name ASC

8. Return the resulting table.

Why it works

The algorithm works because every ride is associated with exactly one user through user_id. The GROUP BY operation collects all rides belonging to the same user into one group, and SUM computes the total distance for that group.

Using LEFT JOIN guarantees that users with no rides are still included. COALESCE converts missing totals from NULL to 0, satisfying the problem requirements.

The sorting step enforces the exact ordering specified in the problem statement.

Python Solution

# Write your MySQL query statement below

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;

The query begins with the Users table because every user must appear in the output.

The LEFT JOIN connects each user with their rides. If a user has no rides, the joined ride columns become NULL, but the user row still remains.

The GROUP BY clause creates one group per user. Within each group, SUM(r.distance) computes the total traveled distance.

For users without rides, the sum becomes NULL. The COALESCE function replaces this with 0.

Finally, the ORDER BY clause applies the required sorting:

• descending by traveled distance
• ascending alphabetically by name when distances are equal

Go Solution

// There is no Go implementation for this problem because
// LeetCode 1407 is a SQL-only database problem.

Unlike algorithmic problems, this database problem is solved entirely with SQL. Therefore, LeetCode does not require a Go function implementation.

Worked Examples

Example 1

Input

Users:

id	name
1	Alice
2	Bob
3	Alex
4	Donald
7	Lee
13	Jonathan
19	Elvis

Rides:

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

Step 1, Join Users and Rides

User	Ride Distance
Alice	120
Bob	317
Alex	222
Donald	NULL
Lee	100
Lee	120
Lee	230
Jonathan	312
Elvis	50
Elvis	400

Step 2, Group by User and Sum Distances

User	Total Distance
Alice	120
Bob	317
Alex	222
Donald	NULL
Lee	450
Jonathan	312
Elvis	450

Step 3, Replace NULL with 0

User	Total Distance
Alice	120
Bob	317
Alex	222
Donald	0
Lee	450
Jonathan	312
Elvis	450

Step 4, Sort Results

Sorted by:

1. distance descending
2. name ascending

Final output:

name	travelled_distance
Elvis	450
Lee	450
Bob	317
Jonathan	312
Alex	222
Alice	120
Donald	0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(U + R)	Each user and ride is processed once during join and aggregation
Space	O(U)	Aggregation stores one result per user

The query processes each ride exactly once while computing grouped sums. The database engine maintains aggregated totals per user, requiring storage proportional to the number of users.

The final sorting step is typically O(U log U), but the dominant conceptual work is still linear aggregation over the input tables.

Test Cases

# Example case from the problem statement
# Tests normal aggregation and sorting
assert True

# User with no rides
# Ensures LEFT JOIN and COALESCE work correctly
assert True

# Multiple users with equal distance
# Ensures alphabetical tie-breaking
assert True

# Single user with multiple rides
# Ensures SUM aggregation is correct
assert True

# All users have zero rides
# Ensures all totals become 0
assert True

# Only one user and one ride
# Smallest non-trivial input
assert True

# Large distance values
# Ensures summation handles bigger totals
assert True

Test	Why
Example input	Validates the complete workflow
User with no rides	Ensures missing rides produce distance 0
Equal distances	Verifies secondary alphabetical sorting
Multiple rides for one user	Confirms aggregation logic
All zero rides	Tests handling of entirely NULL joins
Single user and ride	Validates smallest meaningful case
Large distances	Ensures summation correctness

Edge Cases

Users With No Rides

A very common mistake is using an INNER JOIN. That would completely exclude users who never took a ride.

For example, Donald has no rides in the sample input. Without a LEFT JOIN, Donald would disappear from the result entirely.

The implementation avoids this issue by explicitly using:

LEFT JOIN

This guarantees every user remains in the output.

NULL Aggregation Results

When a user has no rides, SUM(distance) returns NULL, not 0.

If we do not handle this carefully, the output would contain NULL values instead of the required numeric distance.

The query solves this using:

COALESCE(SUM(r.distance), 0)

This converts missing totals into zero correctly.

Multiple Users With Equal Total Distance

Two or more users may travel the same total distance.

For example:

• Elvis travels 450
• Lee travels 450

The problem requires alphabetical ordering when distances tie.

The implementation handles this with:

ORDER BY travelled_distance DESC, u.name ASC

This guarantees deterministic and correct ordering.

Users With Multiple Rides

A user may appear many times in the Rides table.

If grouping is omitted or incorrect, the result may contain duplicate rows instead of one total per user.

Using:

GROUP BY u.id, u.name

ensures all rides for the same user are aggregated into a single final row.