Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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.
Example 1:
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
target.target.Example 2:
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation:
There is only one car, hence there is only one fleet.Example 3:
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
target.Constraints:
n == position.length == speed.length1 <= n <= 1050 < target <= 1060 <= position[i] < targetposition are unique.0 < speed[i] <= 106Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Stack
12 [10,8,0,5,3] [2,4,1,1,3]
10 [3] [3]
100 [0,2,4] [4,2,1]
car-fleet-ii)count-collisions-on-a-road)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #853: Car Fleet
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
Integer[] idx = new Integer[n];
Arrays.setAll(idx, i -> i);
Arrays.sort(idx, (i, j) -> position[j] - position[i]);
int ans = 0;
double pre = 0;
for (int i : idx) {
double t = 1.0 * (target - position[i]) / speed[i];
if (t > pre) {
++ans;
pre = t;
}
}
return ans;
}
}
// Accepted solution for LeetCode #853: Car Fleet
func carFleet(target int, position []int, speed []int) (ans int) {
n := len(position)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool { return position[idx[j]] < position[idx[i]] })
var pre float64
for _, i := range idx {
t := float64(target-position[i]) / float64(speed[i])
if t > pre {
ans++
pre = t
}
}
return
}
# Accepted solution for LeetCode #853: Car Fleet
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
idx = sorted(range(len(position)), key=lambda i: position[i])
ans = pre = 0
for i in idx[::-1]:
t = (target - position[i]) / speed[i]
if t > pre:
ans += 1
pre = t
return ans
// Accepted solution for LeetCode #853: Car Fleet
impl Solution {
pub fn car_fleet(target: i32, position: Vec<i32>, speed: Vec<i32>) -> i32 {
let mut position_speed_pair: Vec<(f64, f64)> = position
.iter()
.map(|x| *x as f64)
.zip(speed.iter().map(|x| *x as f64))
.collect();
position_speed_pair.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
let mut stack = vec![];
for (pos, speed) in position_speed_pair.iter().rev() {
stack.push((target as f64 - pos) / speed);
if stack.len() >= 2 && stack.last() <= stack.get(stack.len() - 2) {
stack.pop();
}
}
stack.len() as i32
}
}
// Accepted solution for LeetCode #853: Car Fleet
function carFleet(target: number, position: number[], speed: number[]): number {
const n = position.length;
const idx = Array(n)
.fill(0)
.map((_, i) => i)
.sort((i, j) => position[j] - position[i]);
let ans = 0;
let pre = 0;
for (const i of idx) {
const t = (target - position[i]) / speed[i];
if (t > pre) {
++ans;
pre = t;
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.