LeetCode 3829 - Design Ride Sharing System

Difficulty: 🟡 Medium
Topics: Hash Table, Design, Queue, Data Stream

Solution

Problem Understanding

The problem asks us to design a ride sharing system that manages both riders and drivers as they enter the system, and to match them in a first-come, first-served order. The system must track riders who are waiting for rides, drivers who are available, and support canceling rider requests.

Inputs include rider and driver IDs, which are integers in the range 1 to 1000. Operations include adding riders and drivers, matching the earliest available driver with the earliest waiting rider, and canceling a rider request if it exists and has not yet been matched. The output for matching should always return a pair [driverId, riderId] if a match is possible, or [-1, -1] otherwise.

Constraints guarantee uniqueness of rider IDs among riders and driver IDs among drivers. Each rider or driver will only be added once. The total number of operations is at most 1000, which means we do not need extremely heavy optimizations, but we should aim for an efficient, clear solution.

Important edge cases include trying to match when no riders or drivers are available, canceling a rider who is not in the system or has already been matched, and adding multiple riders or drivers before any match occurs.

Approaches

A brute-force approach would maintain two lists: one for riders and one for drivers. To match, we would always take the first driver and first rider in the respective lists. To cancel a rider, we would have to scan the entire list to remove the rider. While this approach is simple and correct, canceling a rider takes O(n) time in the worst case, which could be slow if there are many riders in the queue.

The optimal approach uses a queue for maintaining order of riders and drivers, combined with a set for fast lookup and removal of riders when canceled. The queue preserves the first-come, first-served order, while the set allows O(1) checking whether a rider is still valid in the system. When matching, we remove riders and drivers from the front of the queues and from the set, ensuring correctness without scanning the entire queue. This achieves O(1) amortized operations for adding, matching, and canceling.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per cancel, O(1) per match	O(n)	Cancelling requires scanning the rider list
Optimal	O(1) amortized	O(n)	Uses queue + set to maintain order and fast lookup

Algorithm Walkthrough

Initialize the system with two queues: one for riders and one for drivers, and a set to store active rider IDs.
When addRider(riderId) is called, append the rider ID to the rider queue and add it to the active rider set.
When addDriver(driverId) is called, append the driver ID to the driver queue.
When matchDriverWithRider() is called, check if both queues have at least one element. If either is empty, return [-1, -1].
Otherwise, remove the earliest driver from the driver queue.
Remove the earliest rider from the rider queue, skipping any riders who have canceled (i.e., not present in the active rider set). Once a valid rider is found, remove it from the active set.
Return the [driverId, riderId] pair.
When cancelRider(riderId) is called, remove the rider from the active rider set. The rider remains in the queue, but will be skipped during matching.

Why it works: The queues guarantee that the order of arrival is preserved. Using a set for active riders ensures that canceled riders are not matched. This combination ensures that matching always pairs the earliest available driver with the earliest valid rider, fulfilling the problem requirements.

Python Solution

from collections import deque
from typing import List

class RideSharingSystem:

    def __init__(self):
        self.rider_queue = deque()
        self.driver_queue = deque()
        self.active_riders = set()

    def addRider(self, riderId: int) -> None:
        self.rider_queue.append(riderId)
        self.active_riders.add(riderId)

    def addDriver(self, driverId: int) -> None:
        self.driver_queue.append(driverId)

    def matchDriverWithRider(self) -> List[int]:
        while self.rider_queue and self.rider_queue[0] not in self.active_riders:
            self.rider_queue.popleft()
        if not self.rider_queue or not self.driver_queue:
            return [-1, -1]
        driverId = self.driver_queue.popleft()
        riderId = self.rider_queue.popleft()
        self.active_riders.remove(riderId)
        return [driverId, riderId]

    def cancelRider(self, riderId: int) -> None:
        self.active_riders.discard(riderId)

This implementation uses deque for queues and a set for active riders. Riders are removed from the active set when canceled or matched, ensuring no invalid matches. The while loop in matchDriverWithRider skips any canceled riders, preserving the first-come, first-served invariant.

Go Solution

package main

type RideSharingSystem struct {
    riderQueue   []int
    driverQueue  []int
    activeRiders map[int]bool
}

func Constructor() RideSharingSystem {
    return RideSharingSystem{
        riderQueue:   []int{},
        driverQueue:  []int{},
        activeRiders: make(map[int]bool),
    }
}

func (this *RideSharingSystem) AddRider(riderId int) {
    this.riderQueue = append(this.riderQueue, riderId)
    this.activeRiders[riderId] = true
}

func (this *RideSharingSystem) AddDriver(driverId int) {
    this.driverQueue = append(this.driverQueue, driverId)
}

func (this *RideSharingSystem) MatchDriverWithRider() []int {
    for len(this.riderQueue) > 0 && !this.activeRiders[this.riderQueue[0]] {
        this.riderQueue = this.riderQueue[1:]
    }
    if len(this.riderQueue) == 0 || len(this.driverQueue) == 0 {
        return []int{-1, -1}
    }
    driverId := this.driverQueue[0]
    this.driverQueue = this.driverQueue[1:]
    riderId := this.riderQueue[0]
    this.riderQueue = this.riderQueue[1:]
    delete(this.activeRiders, riderId)
    return []int{driverId, riderId}
}

func (this *RideSharingSystem) CancelRider(riderId int) {
    delete(this.activeRiders, riderId)
}

In Go, slices are used for queues, and a map represents the active riders set. Removing from the front of a slice requires creating a new slice, but given constraints, this is efficient enough. The logic mirrors the Python version.

Worked Examples

Example 1:

Step	Rider Queue	Driver Queue	Active Riders	Operation	Output
1	[]	[]	{}	addRider(3)	null
2	[3]	[]	{3}	addDriver(2)	null
3	[3,1]	[2]	{1,3}	addRider(1)	null
4	[1]	[]	{1}	matchDriverWithRider()	[2,3]
5	[1]	[5]	{1}	addDriver(5)	null
6	[1]	[5]	{1}	cancelRider(3)	null
7	[]	[]	{}	matchDriverWithRider()	[5,1]
8	[]	[]	{}	matchDriverWithRider()	[-1,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) amortized	Each rider and driver is added/removed at most once, skipping canceled riders is O(1) amortized
Space	O(n)	Stores queues and a set, at most one entry per rider/driver

The key observation is that each rider or driver is ever in memory only once, and canceled riders do not need full list scanning.

Test Cases

# Provided example 1
obj = RideSharingSystem()
obj.addRider(3)
obj.addDriver(2)
obj.addRider(1)
assert obj.matchDriverWithRider() == [2,3]  # match earliest driver and rider
obj.addDriver(5)
obj.cancelRider(3)  # already matched, no effect
assert obj.matchDriverWithRider() == [5,1]
assert obj.matchDriverWithRider() == [-1,-1]  # no drivers or riders left

# Provided example 2
obj = RideSharingSystem()
obj.addRider(8)
obj.addDriver(8)
obj.addDriver(6)
assert obj.matchDriverWithRider() == [8,8]
obj.addRider(2)
obj.cancelR