Watch 9 video solutions for The Latest Time to Catch a Bus, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by Web Mickey has 2,271 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the ith bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the jth passenger. All bus departure times are unique. All passenger arrival times are unique.
You are given an integer capacity, which represents the maximum number of passengers that can get on each bus.
When a passenger arrives, they will wait in line for the next available bus. You can get on a bus that departs at x minutes if you arrive at y minutes where y <= x, and the bus is not full. Passengers with the earliest arrival times get on the bus first.
More formally when a bus arrives, either:
capacity or fewer passengers are waiting for a bus, they will all get on the bus, orcapacity passengers with the earliest arrival times will get on the bus.Return the latest time you may arrive at the bus station to catch a bus. You cannot arrive at the same time as another passenger.
Note: The arrays buses and passengers are not necessarily sorted.
Example 1:
Input: buses = [10,20], passengers = [2,17,18,19], capacity = 2 Output: 16 Explanation: Suppose you arrive at time 16. At time 10, the first bus departs with the 0th passenger. At time 20, the second bus departs with you and the 1st passenger. Note that you may not arrive at the same time as another passenger, which is why you must arrive before the 1st passenger to catch the bus.
Example 2:
Input: buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2 Output: 20 Explanation: Suppose you arrive at time 20. At time 10, the first bus departs with the 3rd passenger. At time 20, the second bus departs with the 5th and 1st passengers. At time 30, the third bus departs with the 0th passenger and you. Notice if you had arrived any later, then the 6th passenger would have taken your seat on the third bus.
Constraints:
n == buses.lengthm == passengers.length1 <= n, m, capacity <= 1052 <= buses[i], passengers[i] <= 109buses is unique.passengers is unique.Problem Overview: You are given departure times of buses, arrival times of passengers, and a capacity for each bus. Passengers board the earliest bus they can catch until capacity is full. The task is to determine the latest possible time you can arrive at the station and still board a bus, while ensuring your arrival time does not match any existing passenger time.
Approach 1: Sorted Two-Pointer Simulation (O(n log n + m log m) time, O(1) extra space)
Sort both the buses and passengers arrays. Then simulate the boarding process using two pointers. Iterate through buses in chronological order and greedily assign passengers who arrive before or at the bus departure until the bus reaches capacity. After processing the last bus, determine the latest valid arrival time: if the bus still has space, you can arrive exactly at its departure; if it is full, the candidate time becomes one minute before the last boarded passenger. Decrease the time while it conflicts with existing passenger arrival times. The technique relies on sorted traversal and pointer advancement, a common pattern in Two Pointers and Array problems.
Approach 2: Greedy Backtrack with Binary Search (O((n + m) log m) time, O(1) space)
Another strategy treats the answer as a search problem. First sort buses and passengers. Use Binary Search to test candidate arrival times. For each candidate time, simulate whether boarding is possible by greedily assigning passengers to buses while including the hypothetical arrival. If the candidate time allows boarding, move the search window later; otherwise move earlier. After finding the latest feasible time, backtrack if that timestamp coincides with an existing passenger arrival. This approach separates feasibility checking from answer discovery, which can be useful when constraints grow or the boarding rule becomes more complex.
Recommended for interviews: The sorted two-pointer simulation is the expected solution. It directly models the boarding process and runs in O(n log n + m log m) due to sorting. Interviewers prefer this approach because the logic is transparent and easy to reason about. The binary-search variant shows deeper algorithmic thinking but adds unnecessary complexity for this specific problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorted Two-Pointer Simulation | O(n log n + m log m) | O(1) | Best general solution. Efficient when buses and passengers can be sorted and simulated sequentially. |
| Greedy Backtrack with Binary Search | O((n + m) log m) | O(1) | Useful when treating the answer as a search space or when feasibility checks are easier than direct computation. |