Design Ride Sharing System - Video Solutions
Design Ride Sharing System | LeetCode 3829 | Weekly Contest 487
Design Ride Sharing System - Video Solution
Watch 5 video solutions for Design Ride Sharing System, a medium level problem involving Hash Table, Design, Queue. This walkthrough by Sanyam IIT Guwahati has 522 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 givenriderId.void addDriver(int driverId)Adds a new driver with the givendriverId.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 whereresult = [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 givenriderIdif the rider exists and has not yet been matched.
Example 1:
Input:
["RideSharingSystem", "addRider", "addDriver", "addRider", "matchDriverWithRider", "addDriver", "cancelRider", "matchDriverWithRider", "matchDriverWithRider"]
[[], [3], [2], [1], [], [5], [3], [], []]
Output:
[null, null, null, null, [2, 3], null, null, [5, 1], [-1, -1]]
Explanation
RideSharingSystem rideSharingSystem = new RideSharingSystem(); // Initializes the systemrideSharingSystem.addRider(3); // rider 3 joins the queue
rideSharingSystem.addDriver(2); // driver 2 joins the queue
rideSharingSystem.addRider(1); // rider 1 joins the queue
rideSharingSystem.matchDriverWithRider(); // returns [2, 3]
rideSharingSystem.addDriver(5); // driver 5 becomes available
rideSharingSystem.cancelRider(3); // rider 3 is already matched, cancel has no effect
rideSharingSystem.matchDriverWithRider(); // returns [5, 1]
rideSharingSystem.matchDriverWithRider(); // returns [-1, -1]
Example 2:
Input:
["RideSharingSystem", "addRider", "addDriver", "addDriver", "matchDriverWithRider", "addRider", "cancelRider", "matchDriverWithRider"]
[[], [8], [8], [6], [], [2], [2], []]
Output:
[null, null, null, null, [8, 8], null, null, [-1, -1]]
Explanation
RideSharingSystem rideSharingSystem = new RideSharingSystem(); // Initializes the systemrideSharingSystem.addRider(8); // rider 8 joins the queue
rideSharingSystem.addDriver(8); // driver 8 joins the queue
rideSharingSystem.addDriver(6); // driver 6 joins the queue
rideSharingSystem.matchDriverWithRider(); // returns [8, 8]
rideSharingSystem.addRider(2); // rider 2 joins the queue
rideSharingSystem.cancelRider(2); // rider 2 cancels
rideSharingSystem.matchDriverWithRider(); // returns [-1, -1]
Constraints:
1 <= riderId, driverId <= 1000- Each
riderIdis unique among riders and is added at most once. - Each
driverIdis unique among drivers and is added at most once. - At most 1000 calls will be made in total to
addRiderāāāāāāā,addDriver,matchDriverWithRider, andcancelRider.
Approach Overview
Problem Overview: Design a ride sharing system that processes a continuous stream of ride requests and driver availability updates. The system must efficiently match riders with drivers while maintaining fast lookups and ordered processing of requests.
Approach 1: Queue Simulation + Linear Search (O(n) per operation, O(n) space)
The straightforward implementation uses a queue to store incoming ride requests and a list or map of available drivers. Each time a request arrives, you iterate through the driver list to find a suitable match. When a driver becomes available, you scan the queued requests to assign the earliest compatible rider. This approach mirrors the real-world first-come-first-served process but requires scanning potentially many elements for each assignment.
The key operations are queue insertion for incoming requests and linear iteration for matching. While simple to implement, the repeated scans cause O(n) time per match operation, which becomes slow as the number of riders and drivers grows. Space complexity remains O(n) because all active requests and drivers must be stored in memory.
Approach 2: Sorted Set + Hash Table (O(log n) per operation, O(n) space)
A more scalable design combines a sorted structure for ordering with a hash table for constant-time lookups. The hash table maps rider or driver IDs to their current state, while a sorted set maintains ordering based on attributes such as request time, priority, or distance. This allows the system to always retrieve the most suitable match without scanning the entire dataset.
When a new ride request arrives, insert it into the sorted set and record its metadata in the hash table. When a driver becomes available, query the sorted set to fetch the best candidate in O(log n) time. After a match, remove both entities from the sorted structure and update the hash table. This design supports fast updates and efficient matching even under heavy request streams, which is typical in data stream style problems.
The combination works because the sorted set guarantees efficient ordering while the hash table provides direct access to objects during updates or cancellations. Insertions, deletions, and queries all run in O(log n) time, making the system responsive even with thousands of active rides.
Recommended for interviews: Interviewers typically expect the Sorted Set + Hash Table design. A basic queue simulation shows you understand the workflow, but the optimized design demonstrates knowledge of scalable system design and efficient data structures. Mentioning why linear scans fail at scale and replacing them with ordered retrieval is the key insight that signals strong problem-solving ability.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Queue Simulation + Linear Search | O(n) per match | O(n) | Simple prototype or when the number of drivers and riders is very small |
| Sorted Set + Hash Table | O(log n) per operation | O(n) | Production-scale systems or interview solutions requiring efficient matching |