Convoys at the Gate
Cars drive along a one-lane road toward a gate at position gate. Car i starts at position[i] and drives speed[i] positions per hour. A car can never pass the car ahead of it: when it catches up, it slows down and they drive on together as one convoy at the slower speed. A car that catches up exactly at the gate joins that convoy too.
Return the number of cars in each convoy, in the order in which the convoys reach the gate, or an empty list if there are no cars.
Example 1
The car at 12 needs 4 hours alone, the same as the car at 16, so they meet right at the gate. The other two cars never catch up.
Example 2
The fast car would arrive after 2 hours, but it is stuck behind the car that needs 5.
Constraints
1 <= gate <= 10000 <= len(position) == len(speed) <= 1000 <= position[i] < gate, all different1 <= speed[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Stacks and queues problems
- Daily TemperaturesMedium
- Decode StringMedium
- Flip and Double BracketsMedium
- Keep the Digits, One of Each LetterMedium
- Largest Open PlotMedium
- Longest Balanced PieceMedium
- Longest Steady StretchMedium
- Most Pieces to Sort SeparatelyMedium