Car Fleet
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 1
- Core for
- 9 roles
The problem
There are n cars traveling to the same destination at different speeds along a one-lane road. A car fleet is a group of cars driving at the same position and speed. A faster car behind a slower car will catch up and join the slower car's fleet. Return the number of car fleets that arrive at the destination.
Example 1
- Input
- target = 15, position = [12,9,1,6,4], speed = [3,5,2,2,4]
- Output
- 4
- Why
- Arrival times from the front: 1h, 1.2h, 4.5h, 2.75h, 7h. The 1.2h car catches nobody, the 2.75h car catches the 4.5h one, so 4 fleets reach the target.
Example 2
- Input
- target = 8, position = [5], speed = [1]
- Output
- 1
- Why
- A single car is its own fleet.
Constraints
- n == position.length == speed.length
- 1 <= n <= 10^5
- 0 < target <= 10^6
- 0 <= position[i] < target
- All positions are unique
- 1 <= speed[i] <= 10^6
How to think about it
Updated 2026-09-29Cars cannot pass each other, so a car closer to the destination sets the pace for any trailing car that reaches it. Calculate the exact time each car would take to reach target if unimpeded. Process cars from closest to target back to furthest: if a trailing car takes less or equal time than the fleet ahead, it merges into it; if it takes longer, it anchors a brand new fleet.
Approaches, worst first
Simulate step by step
time O(n^2) · space O(n)
Advance time or collision events incrementally, detecting pairwise intersections and merging fleets. Fractional collision times require floating point event queues and repeated updates, making the simulation tedious and prone to precision decay.
Sort by position, sweep arrivalsWrite this one
time O(n log n) · space O(n)
Pair each position with its arrival time `(target - position) / speed` and sort descending by position. Traverse from front to back, maintaining the maximum arrival time seen so far. Whenever a car's time exceeds this maximum, it cannot catch the lead fleet, incrementing the fleet count and resetting the pace.
Where people lose marks · 3
- Integer division when computing arrival times `(target - pos) / speed` truncates fractional hours, falsely treating cars that arrive slightly later as having merged.
- Sorting by speed instead of starting position: fleet membership is strictly constrained by road order because cars cannot pass each other regardless of raw top speed.
- Failing to handle single-car inputs correctly: a single car always forms exactly 1 fleet.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .