FunctionRacerProblemsRace

Convoys at the Gate

MediumStacks and queuesPython, JavaScript, TypeScript, Java, C++

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

gate 20
position [16,12,6,2]
speed [1,2,3,1]
returns [2,1,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

gate 10
position [0,5]
speed [5,1]
returns [2]

The fast car would arrive after 2 hours, but it is stuck behind the car that needs 5.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Stacks and queues problems