Car Fleet

MediumStackmonotonic stack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are n cars driving along a single-lane road toward the same destination, which sits at mile-marker target. Cars are not allowed to pass one another. You are given two integer arrays, position and speed, both of length n. The car at index i starts at position[i] miles from the start and travels at speed[i] miles per unit of time. Every car drives toward target and never moves backward. When a faster car catches up to a slower car ahead of it, it cannot overtake. Instead it slows down and matches the slower car's speed, and from that moment the two travel together as a single group. A group of one or more cars that arrives at the destination bumper-to-bumper is called a **fleet**. A single car that reaches target without ever catching another counts as a fleet of size one. Note that a car that catches up to a fleet exactly at the destination is considered part of that same fleet. Return the number of distinct car fleets that will arrive at the destination.

Examples

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
The cars at positions 10 and 8 reach the target together as one fleet (meeting at marker 12). The car at position 0 travels alone as a second fleet. The cars at positions 5 and 3 meet at marker 6 and arrive together as a third fleet. That gives 3 fleets total.
Input: target = 10, position = [3], speed = [3]
Output: 1
A single car is always exactly one fleet.
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
The fastest car starts farthest back but catches the others before the destination, so all three merge into a single fleet.

Constraints

  • `n == position.length == speed.length`
  • `0 <= n <= 10^5`
  • `0 < target <= 10^6`
  • `0 <= position[i] < target`
  • `0 < speed[i] <= 10^6`
  • All values in `position` are unique.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More monotonic stack problems