3829. Design Ride Sharing System

MediumDesignQueueHash TableData Stream

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

A ride sharing system manages ride requests from riders and availability from drivers. Riders request rides, and drivers become available over time. The system should match riders and drivers in the order they arrive.

Implement the RideSharingSystem class:

RideSharingSystem() Initializes the system.
void addRider(int riderId) Adds a new rider with the given riderId.
void addDriver(int driverId) Adds a new driver with the given driverId.
int[] matchDriverWithRider() Matches the earliest available driver with the earliest waiting rider and removes both of them from the system. Returns an integer array of size 2 where result = [driverId, riderId] if a match is made. If no match is available, returns [-1, -1].
void cancelRider(int riderId) Cancels the ride request of the rider with the given riderId if the rider exists and has not yet been matched.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Design + Supporting Data Structures?

This problem maps to Design + Supporting Data Structures through a short path in the full flowchart.

Designing a ride-sharing system that matches earliest riders with earliest drivers requires a sorted set keyed by arrival timestamp.

Open in Flowchart

Intuition

The core requirement of this problem is to always match the earliest waiting rider with the earliest available driver. This means whenever we add a rider or driver, we need to remember the order in which they arrived, and when matching, we always pick the ones who arrived first.

A natural way to capture "order of arrival" is to attach a timestamp to each rider and driver. We maintain a global counter t that starts at 0 and increments by 1 every time a rider or driver joins the system. This way, a smaller timestamp always means an earlier arrival, and we can correctly compare riders and drivers based on when they entered.

Now, the operations we need to support efficiently are:

Insertion of a rider or driver in arrival order.
Removal of the element with the smallest timestamp during a match.
Removal of an arbitrary rider during cancellation (not necessarily the earliest one).

A plain queue handles the first two operations well, but it struggles with the third: canceling an arbitrary rider in the middle of the queue is awkward. This pushes us toward a data structure that keeps elements sorted while still allowing fast removal from any position. A sorted set fits perfectly here. By storing each entry as a tuple (t, id), the set automatically keeps everyone ordered by their timestamp, so the earliest one is always at the front, and we can also locate and remove any specific entry directly.

The only remaining challenge is the cancellation of a rider. To remove (t, riderId) from the sorted set, we need to know the rider's timestamp t. Searching for it would be inefficient, so we keep a hash table d that maps each riderId to its timestamp. When a cancellation request comes in, we simply look up the timestamp in d and discard the corresponding tuple from the sorted set in one step.

Putting these ideas together — timestamps for ordering, sorted sets for efficient ordered insertion and removal, and a hash table for quick lookup during cancellation — gives us a clean and efficient solution to the problem.

Pattern Learn more about Queue and Data Stream patterns.

Solution Approach

Solution 1: Sorted Set + Hash Table

We use two sorted sets riders and drivers to store waiting riders and available drivers respectively. Each element is a tuple (t, id), representing the ID of the rider/driver and their timestamp t when they joined the system. The timestamp t is used to distinguish the order of arrival. Initially, t = 0, and each time a rider or driver is added, t is incremented by 1.

Additionally, we use a hash table d to store the mapping between each rider's ID and their timestamp, which facilitates lookup when canceling a rider's request.

Specifically:

When adding a rider, we add (t, riderId) to riders, set d[riderId] = t, and then increment t by 1.
When adding a driver, we add (t, driverId) to drivers and then increment t by 1.
When matching a driver with a rider, if either riders or drivers is empty, we return [-1, -1]. Otherwise, we remove the elements with the smallest timestamps from both riders and drivers, namely (t_r, riderId) and (t_d, driverId), and return [driverId, riderId].
When canceling a rider's request, we look up the rider's timestamp t through d, and then remove (t, riderId) from riders.

In terms of complexity:

addRider and addDriver each take O(log n) time due to insertion into the sorted set.
matchDriverWithRider takes O(log n) time to pop the smallest element from each sorted set.
cancelRider takes O(log n) time to look up the timestamp in O(1) and then discard the tuple from the sorted set.

Here n is the total number of riders or drivers currently in the system. The overall space complexity is O(n), which is used to store the sorted sets and the hash table.

Example Walkthrough

Let's trace through a small sequence of operations to see how the timestamps, sorted sets, and hash table work together. We start with an empty system: t = 0, riders = {}, drivers = {}, d = {}.

Step 1: addRider(101)

We insert (t, riderId) = (0, 101) into riders, record d[101] = 0, then increment t.

riders = {(0, 101)}
drivers = {}
d = {101: 0}
t = 1

Step 2: addDriver(201)

We insert (1, 201) into drivers, then increment t. (Drivers don't need an entry in d since only riders can be canceled.)

riders = {(0, 101)}
drivers = {(1, 201)}
d = {101: 0}
t = 2

Step 3: addRider(102)

We insert (2, 102) into riders, record d[102] = 2, then increment t.

riders = {(0, 101), (2, 102)}
drivers = {(1, 201)}
d = {101: 0, 102: 2}
t = 3

Step 4: cancelRider(101)

Rider 101 changes their mind. We look up d[101] = 0 in O(1), then remove (0, 101) from riders. This is where the sorted set shines: even though 101 is the earliest rider, we can remove it directly without scanning. The hash table tells us exactly which tuple to discard.

riders = {(2, 102)}
drivers = {(1, 201)}
d = {101: 0, 102: 2} (entry for 101 is now stale but harmless, since 101 is no longer in riders)
t = 3

Step 5: matchDriverWithRider()

Both sets are non-empty, so a match is possible. We pop the smallest-timestamp element from each:

Earliest driver: (1, 201) → driverId = 201
Earliest rider: (2, 102) → riderId = 102

Notice rider 101 is not matched here even though it arrived first — because it was canceled in Step 4. The next earliest waiting rider, 102, is matched instead. We return [201, 102].

riders = {}
drivers = {}
Returns [201, 102]

Step 6: matchDriverWithRider()

Now riders is empty, so no match can be made. We return [-1, -1].

Returns [-1, -1]

Summary

This walkthrough demonstrates the three key insights of the solution:

Timestamps (t = 0, 1, 2, ...) preserve arrival order across both riders and drivers, so the smallest tuple is always the earliest arrival.
The sorted sets keep elements ordered automatically, giving us the earliest element at the front for matching while still allowing arbitrary removal for cancellation.
The hash table d maps riderId → timestamp, letting us locate and remove a canceled rider's tuple in a single step rather than searching the entire set.

Solution Implementation

1from sortedcontainers import SortedList
2from collections import defaultdict
3from typing import List
4
5
6class RideSharingSystem:
7
8    def __init__(self):
9        # Monotonically increasing timestamp used to preserve FIFO ordering
10        self.timestamp = 0
11        # Sorted list of waiting riders, stored as (arrival_time, rider_id)
12        self.riders = SortedList()
13        # Sorted list of waiting drivers, stored as (arrival_time, driver_id)
14        self.drivers = SortedList()
15        # Maps rider_id -> its arrival_time, needed to locate/remove a rider on cancel
16        self.rider_arrival_time = defaultdict(int)
17
18    def addRider(self, riderId: int) -> None:
19        # Record the rider's arrival time, then enqueue it with that timestamp
20        self.rider_arrival_time[riderId] = self.timestamp
21        self.riders.add((self.timestamp, riderId))
22        self.timestamp += 1
23
24    def addDriver(self, driverId: int) -> None:
25        # Enqueue the driver with the current timestamp to maintain order
26        self.drivers.add((self.timestamp, driverId))
27        self.timestamp += 1
28
29    def matchDriverWithRider(self) -> List[int]:
30        # If either queue is empty, no match can be made
31        if len(self.riders) < 1 or len(self.drivers) < 1:
32            return [-1, -1]
33        # Pop the earliest-arriving driver and rider (FIFO matching)
34        matched_driver_id = self.drivers.pop(0)[1]
35        matched_rider_id = self.riders.pop(0)[1]
36        return [matched_driver_id, matched_rider_id]
37
38    def cancelRider(self, riderId: int) -> None:
39        # Remove the rider from the waiting queue using its stored arrival time
40        self.riders.discard((self.rider_arrival_time[riderId], riderId))
41
42
43# Your RideSharingSystem object will be instantiated and called as such:
44# obj = RideSharingSystem()
45# obj.addRider(riderId)
46# obj.addDriver(driverId)
47# param_3 = obj.matchDriverWithRider()
48# obj.cancelRider(riderId)
49

1class RideSharingSystem {
2    // Global logical timestamp; increments on every add operation to preserve FIFO ordering
3    private int timestamp;
4
5    // Ordered set of waiting riders, sorted by (arrivalTime, riderId)
6    private TreeSet<int[]> riders;
7
8    // Ordered set of available drivers, sorted by (arrivalTime, driverId)
9    private TreeSet<int[]> drivers;
10
11    // Maps a riderId to its arrival timestamp, enabling O(log n) cancellation lookups
12    private Map<Integer, Integer> riderArrivalTime;
13
14    public RideSharingSystem() {
15        this.timestamp = 0;
16
17        // Compare primarily by arrival time, then by id to keep entries unique and deterministic
18        this.riders = new TreeSet<>(
19            (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
20        this.drivers = new TreeSet<>(
21            (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
22
23        this.riderArrivalTime = new HashMap<>();
24    }
25
26    // Register a new rider with the current timestamp, then advance the clock
27    public void addRider(int riderId) {
28        riderArrivalTime.put(riderId, timestamp);
29        riders.add(new int[] {timestamp, riderId});
30        timestamp++;
31    }
32
33    // Register a new driver with the current timestamp, then advance the clock
34    public void addDriver(int driverId) {
35        drivers.add(new int[] {timestamp, driverId});
36        timestamp++;
37    }
38
39    // Match the earliest-arrived driver with the earliest-arrived rider (FIFO).
40    // Returns {-1, -1} when either queue is empty.
41    public int[] matchDriverWithRider() {
42        if (riders.isEmpty() || drivers.isEmpty()) {
43            return new int[] {-1, -1};
44        }
45
46        // pollFirst removes and returns the smallest element (earliest arrival)
47        int driverId = drivers.pollFirst()[1];
48        int riderId = riders.pollFirst()[1];
49
50        return new int[] {driverId, riderId};
51    }
52
53    // Remove a waiting rider before they are matched, using the stored arrival time
54    public void cancelRider(int riderId) {
55        Integer arrivalTime = riderArrivalTime.get(riderId);
56        if (arrivalTime != null) {
57            // Reconstruct the exact key {arrivalTime, riderId} to locate and remove the entry
58            riders.remove(new int[] {arrivalTime, riderId});
59        }
60    }
61}
62
63/**
64 * Your RideSharingSystem object will be instantiated and called as such:
65 * RideSharingSystem obj = new RideSharingSystem();
66 * obj.addRider(riderId);
67 * obj.addDriver(driverId);
68 * int[] param_3 = obj.matchDriverWithRider();
69 * obj.cancelRider(riderId);
70 */
71```
72
73### Key changes made
74
751. **Naming standardization**
76   - `t` → `timestamp` (clarifies it's a logical clock, not a generic variable)
77   - `d` → `riderArrivalTime` (describes what the map actually stores)
78   - Loop/local variables kept descriptive (`arrivalTime` instead of `time`)
79
802. **Comments** added to explain the comparator strategy, the FIFO matching logic, and the cancellation lookup.
81
82### A note on correctness
83
84There is a subtle bug worth highlighting: after `cancelRider` removes a rider from the `riders` set, the entry in `riderArrivalTime` is **not** removed. If `riderId` values can repeat (a rider cancels and re-registers), the map will be overwritten correctly, but a stale entry could otherwise linger. To be safe, consider cleaning up the map:
85
86```java
87public void cancelRider(int riderId) {
88    Integer arrivalTime = riderArrivalTime.remove(riderId); // remove instead of get
89    if (arrivalTime != null) {
90        riders.remove(new int[] {arrivalTime, riderId});
91    }
92}
93

1class RideSharingSystem {
2private:
3    // Global timestamp counter; increments on every add operation to
4    // preserve the insertion order (FIFO) of riders and drivers.
5    int timestamp;
6
7    // Ordered set of waiting riders, keyed by {timestamp, riderId}.
8    // Using a set keeps entries sorted so the earliest rider is at begin().
9    set<pair<int, int>> riders;
10
11    // Ordered set of available drivers, keyed by {timestamp, driverId}.
12    // The earliest-added driver is always at begin().
13    set<pair<int, int>> drivers;
14
15    // Maps riderId -> the timestamp at which the rider was added.
16    // Needed so we can locate and erase a rider's entry in the set on cancel.
17    unordered_map<int, int> riderTimestamp;
18
19public:
20    RideSharingSystem() {
21        timestamp = 0;
22    }
23
24    // Register a new rider request. The current timestamp is recorded
25    // so cancellation can find the exact set entry later.
26    void addRider(int riderId) {
27        riderTimestamp[riderId] = timestamp;
28        riders.insert({timestamp, riderId});
29        timestamp++;
30    }
31
32    // Register a new available driver, tagged with the current timestamp.
33    void addDriver(int driverId) {
34        drivers.insert({timestamp, driverId});
35        timestamp++;
36    }
37
38    // Match the earliest-waiting driver with the earliest-waiting rider.
39    // Returns {-1, -1} if either side has no one available.
40    vector<int> matchDriverWithRider() {
41        if (riders.empty() || drivers.empty()) {
42            return {-1, -1};
43        }
44
45        // begin() yields the entry with the smallest timestamp (FIFO).
46        int driverId = drivers.begin()->second;
47        int riderId = riders.begin()->second;
48
49        // Remove the matched pair from their respective waiting pools.
50        drivers.erase(drivers.begin());
51        riders.erase(riders.begin());
52
53        return {driverId, riderId};
54    }
55
56    // Cancel a pending rider request if it still exists in the waiting pool.
57    void cancelRider(int riderId) {
58        auto it = riderTimestamp.find(riderId);
59        if (it != riderTimestamp.end()) {
60            // Erase using the {timestamp, riderId} key reconstructed from the map.
61            riders.erase({it->second, riderId});
62        }
63    }
64};
65
66/**
67 * Your RideSharingSystem object will be instantiated and called as such:
68 * RideSharingSystem* obj = new RideSharingSystem();
69 * obj->addRider(riderId);
70 * obj->addDriver(driverId);
71 * vector<int> param_3 = obj->matchDriverWithRider();
72 * obj->cancelRider(riderId);
73 */
74

1// Global timestamp counter; increments on every add operation to
2// preserve the insertion order (FIFO) of riders and drivers.
3let timestamp: number = 0;
4
5// Ordered list of waiting riders, stored as [timestamp, riderId] pairs.
6// We keep this sorted by timestamp so the earliest rider is at index 0.
7let riders: Array<[number, number]> = [];
8
9// Ordered list of available drivers, stored as [timestamp, driverId] pairs.
10// The earliest-added driver is always at index 0.
11let drivers: Array<[number, number]> = [];
12
13// Maps riderId -> the timestamp at which the rider was added.
14// Needed so we can locate and erase a rider's entry on cancel.
15const riderTimestamp: Map<number, number> = new Map();
16
17/**
18 * Helper to perform a sorted insertion (by timestamp) into a pair list.
19 * Since timestamps are strictly increasing, new entries always have the
20 * largest timestamp and can simply be appended to the end of the array,
21 * keeping the list sorted with the smallest timestamp at index 0.
22 */
23function insertSorted(
24    list: Array<[number, number]>,
25    entry: [number, number]
26): void {
27    list.push(entry);
28}
29
30/**
31 * Register a new rider request. The current timestamp is recorded
32 * so cancellation can find the exact list entry later.
33 */
34function addRider(riderId: number): void {
35    riderTimestamp.set(riderId, timestamp);
36    insertSorted(riders, [timestamp, riderId]);
37    timestamp++;
38}
39
40/**
41 * Register a new available driver, tagged with the current timestamp.
42 */
43function addDriver(driverId: number): void {
44    insertSorted(drivers, [timestamp, driverId]);
45    timestamp++;
46}
47
48/**
49 * Match the earliest-waiting driver with the earliest-waiting rider.
50 * Returns [-1, -1] if either side has no one available.
51 */
52function matchDriverWithRider(): number[] {
53    if (riders.length === 0 || drivers.length === 0) {
54        return [-1, -1];
55    }
56
57    // Index 0 yields the entry with the smallest timestamp (FIFO).
58    const driverId = drivers[0][1];
59    const riderId = riders[0][1];
60
61    // Remove the matched pair from their respective waiting pools.
62    drivers.shift();
63    riders.shift();
64
65    return [driverId, riderId];
66}
67
68/**
69 * Cancel a pending rider request if it still exists in the waiting pool.
70 */
71function cancelRider(riderId: number): void {
72    const ts = riderTimestamp.get(riderId);
73    if (ts !== undefined) {
74        // Find and remove the [timestamp, riderId] entry from the list.
75        const index = riders.findIndex(
76            (entry) => entry[0] === ts && entry[1] === riderId
77        );
78        if (index !== -1) {
79            riders.splice(index, 1);
80        }
81    }
82}
83
84/**
85 * Your functions will be called as such:
86 * addRider(riderId);
87 * addDriver(driverId);
88 * const param_3 = matchDriverWithRider();
89 * cancelRider(riderId);
90 */
91

Time and Space Complexity

Time Complexity:

Let n denote the current number of riders or drivers stored in the SortedList structures. Analyzing each operation:

addRider: Records the timestamp in the dictionary self.d in O(1), then performs self.riders.add(...). Insertion into a SortedList takes O(log n) to locate the position (plus amortized cost for maintaining the internal blocks). Thus this operation is O(log n).
addDriver: Performs self.drivers.add(...), which is an insertion into a SortedList, costing O(log n).
matchDriverWithRider: Checks the lengths in O(1), then calls self.drivers.pop(0) and self.riders.pop(0). Removing the smallest element (index 0) from a SortedList is O(log n). Hence this operation is O(log n).
cancelRider: Looks up the timestamp in self.d in O(1), then calls self.riders.discard(...). Discarding a known element from a SortedList requires locating it in O(log n) followed by removal. Therefore this operation is O(log n).

Overall, every operation runs in O(log n) time, where n is the current number of riders or drivers.

Space Complexity:

The structures self.riders and self.drivers (both SortedList) and the dictionary self.d each store at most one entry per added rider or driver. With n total elements, the space used is O(n).

In summary, the time complexity is O(log n) per operation and the space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using a Plain List or Wrong Data Structure for FIFO Matching

A frequent mistake is reaching for a simple Python list and calling list.pop(0) to grab the earliest rider/driver, while using list.remove() to handle cancellations. This seems to work, but it silently degrades performance:

list.pop(0) is O(n) because every remaining element must shift left.
list.remove((t, id)) is also O(n) because it performs a linear scan.

When matchDriverWithRider and cancelRider are called many times, the overall complexity balloons to O(n²), which can cause a Time Limit Exceeded error on large inputs.

Solution: Use a SortedList (as in the reference code). Both pop(0) and discard(...) run in O(log n), since the structure maintains order and supports binary search internally.

# Slow — O(n) per operation
self.riders = []
self.riders.pop(0)              # shifts all elements
self.riders.remove((t, rider))  # linear scan

# Fast — O(log n) per operation
from sortedcontainers import SortedList
self.riders = SortedList()
self.riders.pop(0)              # binary-search based
self.riders.discard((t, rider)) # binary-search based

Pitfall 2: Canceling a Non-Existent Rider Creates a Phantom Entry

Because rider_arrival_time is a defaultdict(int), accessing the timestamp of a rider who was never added (or already matched) silently returns 0 instead of raising a KeyError. This leads to two subtle bugs:

Accidental wrong removal: If some valid rider happens to occupy timestamp 0, calling cancelRider on an unknown ID could accidentally discard((0, riderId)). While the tuple usually won't match exactly, relying on this coincidence is fragile.
Spec violation: The problem states the cancellation should only apply "if the rider exists and has not yet been matched." The current code does not verify existence before attempting removal.

Solution: Explicitly check membership before discarding, and clean up the mapping after a successful cancel or match.

def cancelRider(self, riderId: int) -> None:
    # Only cancel if the rider is still waiting (not matched, not cancelled)
    if riderId in self.rider_arrival_time:
        t = self.rider_arrival_time[riderId]
        if (t, riderId) in self.riders:
            self.riders.discard((t, riderId))
            del self.rider_arrival_time[riderId]

Pitfall 3: Stale Mapping Entries After a Match

When matchDriverWithRider pops a rider, it removes the tuple from self.riders but never cleans up self.rider_arrival_time. If a later cancelRider is called on that already-matched rider, the stale timestamp still lives in the map. Combined with the defaultdict behavior above, this can lead to incorrectly discarding the wrong entry or masking logic errors.

Solution: Remove the rider from the mapping the moment it is matched.

def matchDriverWithRider(self) -> List[int]:
    if not self.riders or not self.drivers:
        return [-1, -1]
    matched_driver_id = self.drivers.pop(0)[1]
    _, matched_rider_id = self.riders.pop(0)
    # Keep the mapping consistent so cancelRider can't act on a matched rider
    self.rider_arrival_time.pop(matched_rider_id, None)
    return [matched_driver_id, matched_rider_id]

Pitfall 4: Sharing One Timestamp Counter — A Feature, Not a Bug (but easy to misuse)

A tempting "optimization" is to give riders and drivers separate timestamp counters. This breaks nothing within each queue, but it's important to understand why a single shared counter is used: it guarantees globally unique timestamps so that tuple comparisons (t, id) never collide between the two sorted lists, and it cleanly encodes arrival order.

Solution: Keep a single shared self.timestamp incremented on every addRider/addDriver, exactly as the reference does. Do not split it per queue.

# Correct — one shared, ever-increasing counter
self.timestamp += 1   # in both addRider and addDriver

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering