#2332
The Latest Time to Catch a Bus
MediumArrayTwo PointersBinary SearchSortingSortingTwo Pointers
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n log n) |
| Space | O(1) | O(1) |
💡
Intuition
Time O(n log n)Space O(1)
The optimal solution leverages sorting and a two-pointer technique to efficiently simulate the boarding process. This approach avoids unnecessary checks and directly determines the latest possible arrival time.
⚙️
Algorithm
4 steps- 1Step 1: Sort the buses and passengers arrays.
- 2Step 2: Initialize pointers for buses and passengers, and a variable to track the number of passengers that have boarded.
- 3Step 3: Iterate through each bus, and for each bus, board passengers until the bus is full or there are no more passengers waiting.
- 4Step 4: After processing all buses, check the latest possible time to arrive that is not occupied by any passenger.
solution.py17 lines
1def latestTimeToCatchBus(buses, passengers, capacity):
2 buses.sort()
3 passengers.sort()
4 bus_index = 0
5 passenger_index = 0
6 boarded_passengers = 0
7 while bus_index < len(buses):
8 current_bus = buses[bus_index]
9 boarded_passengers = 0
10 while passenger_index < len(passengers) and passengers[passenger_index] <= current_bus and boarded_passengers < capacity:
11 boarded_passengers += 1
12 passenger_index += 1
13 bus_index += 1
14 latest_time = buses[bus_index - 1] - 1
15 while latest_time in passengers:
16 latest_time -= 1
17 return latest_timeℹ
Complexity note: The time complexity is O(n log n) due to the sorting step, and the boarding simulation runs in O(n), making this approach efficient.
- 1Sorting the buses and passengers allows for efficient processing.
- 2Using a two-pointer technique helps simulate the boarding process without unnecessary checks.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.