← all entries
A-026● Day 262026.05.30mediumleetcode #853neetcode150

Car Fleet

#array#stack#sorting#monotonic-stack
↗ leetcode #853 · car-fleet
01

Problem

· problem
P.026

Car Fleet

↗ leetcode #853

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target. You are given two integer arrays position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour. A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car. A car fleet is a single car or a group of cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet. If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet. Return the number of car fleets that will arrive at the destination.

constraints
  • · 1 ≤ n ≤ 10⁵
  • · 0 < target ≤ 10⁶
  • · 0 ≤ position[i] < target
  • · All position values are unique
  • · 0 < speed[i] ≤ 10⁶
// paraphrased summary — see source for full text
examples
example 1input → output
12
[10,8,0,5,3]
[2,4,1,1,3]
3
example 2input → output
10
[3]
[3]
1
example 3input → output
100
[0,2,4]
[4,2,1]
1
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Why do we need to sort cars by position in descending order?
  • ☐
    What is the key metric to determine if a car joins a fleet?
  • ☐
    When do we remove an element from the stack?
  • ☐
    What if we sorted cars by speed instead of position?
  • ☐
    Do two cars with the exact same arrival time always form the same fleet?
  • ☐
    What happens if we process cars from position 0 forward instead of backward?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Create (position, speed) pairs
○
pair = [(p, s) for p, s in zip(position, speed)]
○
pair = list(zip(position, speed))
○
pair = [(s, p) for p, s in zip(position, speed)]
step 2· Sort pairs by position (descending)
○
pair.sort(reverse=True)
○
pair.sort()
○
pair.sort(key=lambda x: x[1], reverse=True)
step 3· Initialize stack
○
stack = []
○
stack = 0
○
stack = set()
step 4· Calculate arrival time and push to stack│ nested
○
stack.append((target - p) / s)
○
stack.append(target / s)
○
stack.append((target - p) * s)
step 5· Check if current car catches the previous fleet│ nested
○
if len(stack) >= 2 and stack[-1] <= stack[-2]:
○
if len(stack) >= 2 and stack[-1] > stack[-2]:
○
if stack[-1] <= stack[-2]:
step 6· Remove the caught fleet│ │ nested
○
stack.pop()
○
stack.pop()
stack.append((target - p) / s)
○
stack.clear()
step 7· Return the number of fleets
○
return len(stack)
○
return len(pair)
○
return stack[-1] if stack else 0
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
3
        pair = [(p, s) for p, s in zip(position, speed)]
4
        pair.sort(reverse=True)
5
        stack = []
6
        for p, s in pair:  # Reverse Sorted Order
7
            stack.append((target - p) / s)
8
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
9
                stack.pop()
10
        return len(stack)
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
12
[10,8,0,5,3]
[2,4,1,1,3]
→
3
case 2
10
[3]
[3]
→
1
case 3
100
[0,2,4]
[4,2,1]
→
1
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.