Show problems as
Classic problem #853MediumArrayStackSortingMonotonic Stack

Car Fleet

Real-world version: Rafts Reaching the Canal Lock
Tracked in this browser only
Read Car Fleet on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Loaded barges work their way along a single-file canal reach toward a lock. The lock stands lock metres from the top of the reach. Barge i starts starts[i] metres from the top of the reach and covers paces[i] metres a minute in clear water. No two barges start from the same distance, and all of them are under way at minute 0.

The reach is too narrow to pass. If a barge closes right up on the barge ahead, it has to throttle back and hold that barge's pace from then on, and the two carry on to the lock together as a single raft; a raft holds the pace of the slowest barge in it, and rafts join other rafts the same way. Barges that reach the lock at exactly the same minute count as one raft, whether or not they were travelling together before that.

Return how many rafts pass the lock gate.

Examples

Example 1

Input
lock = 12, starts = [0, 6], paces = [2, 1]
Output
1

The barge starting 6 metres along needs 6 minutes to reach the lock and the one starting at the head needs 6 minutes as well, so they get there together and are counted once.

Example 2

Input
lock = 50, starts = [35, 5, 20], paces = [1, 10, 3]
Output
1

The barge at 35 metres reaches the lock 15 minutes in. The other two are held up behind it on the way and pass the lock gate with it.

Example 3

Input
lock = 30, starts = [0, 5, 10, 25], paces = [2, 3, 1, 5]
Output
2

The barge at 25 metres arrives after 1 minute on its own. The barge at 10 metres arrives 20 minutes in, with the barges from 5 and 0 metres held behind it.

Example 4

Input
lock = 100, starts = [0, 10, 20], paces = [5, 5, 5]
Output
3

All three barges hold the same pace, so none of them ever closes on the one in front and each reaches the lock on its own.

Constraints

  • n == starts.length == paces.length
  • 1 <= n <= 10^5
  • 0 < lock <= 10^6
  • 0 <= starts[i] < lock
  • All values in starts are distinct.
  • 0 < paces[i] <= 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def raft_count(lock: int, starts: list[int], paces: list[int]) -> int:
Java
public int raftCount(int lock, int[] starts, int[] paces)

More on the same topics