Problem

Table: Rides

+--------------+------+
| Column Name  | Type |
+--------------+------+
| ride_id      | int  |
| driver_id    | int  |
| passenger_id | int  |
+--------------+------+
ride_id is the column with unique values for this table.
Each row of this table contains the ID of the driver and the ID of the passenger that rode in ride_id.
Note that driver_id != passenger_id.

Write a solution to report the ID of each driver and the number of times they were a passenger.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Input: 
Rides table:
+---------+-----------+--------------+
| ride_id | driver_id | passenger_id |
+---------+-----------+--------------+
| 1       | 7         | 1            |
| 2       | 7         | 2            |
| 3       | 11        | 1            |
| 4       | 11        | 7            |
| 5       | 11        | 7            |
| 6       | 11        | 3            |
+---------+-----------+--------------+
Output: 
+-----------+-----+
| driver_id | cnt |
+-----------+-----+
| 7         | 2   |
| 11        | 0   |
+-----------+-----+
Explanation: 
There are two drivers in all the given rides: 7 and 11.
The driver with ID = 7 was a passenger two times.
The driver with ID = 11 was never a passenger.

Solution

Method 1 – Self Join and Group By

Intuition

For each driver, count how many times their driver_id appears as a passenger_id in the table. Use a left join or subquery to count for each driver.

Approach

  1. Get all unique driver_ids from the Rides table.
  2. For each driver_id, count the number of rows where passenger_id = driver_id.
  3. Return the driver_id and the count.

Code

1
2
3
4

SELECT d.driver_id, COUNT(r.ride_id) AS cnt
FROM (SELECT DISTINCT driver_id FROM Rides) d
LEFT JOIN Rides r ON d.driver_id = r.passenger_id
GROUP BY d.driver_id;
1
2
3
4

SELECT d.driver_id, COUNT(r.ride_id) AS cnt
FROM (SELECT DISTINCT driver_id FROM Rides) d
LEFT JOIN Rides r ON d.driver_id = r.passenger_id
GROUP BY d.driver_id;
1
2
3
4
5
6
7

import pandas as pd
def number_of_times_driver_was_passenger(rides):
    drivers = rides['driver_id'].unique()
    cnt = rides.groupby('passenger_id').size()
    result = pd.DataFrame({'driver_id': drivers})
    result['cnt'] = result['driver_id'].map(cnt).fillna(0).astype(int)
    return result

Complexity

  • ⏰ Time complexity: O(N) where N = #rides
  • 🧺 Space complexity: O(N)