What is the brute force approach and complexity for Car Fleet?

A car leads its own fleet only if no car ahead arrives at the same time or later with time complexity O(N²) and space complexity O(N).

What is the optimal approach and complexity for Car Fleet?

Sort front-to-back; push a car's time only if it is slower than the fleet ahead with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Car Fleet?

Look for key signals in the prompt: "can never pass the car in front" indicates Only cars ahead matter → sort by position and process from the front.; "position and speed" indicates Collapse each car into one number: its time to reach the target.; "catches up … drives at the slower speed" indicates A car joins the fleet ahead if its time ≤ that fleet's time; otherwise it is a new, slower fleet..

Car Fleet

Medium·LeetCode #853 Pro OnlyPattern Transfer

LeetCode

Problem Statement

n cars drive along a one-lane road towards the same destination at mile target. Car i starts at position[i] and drives at speed[i] miles per hour.

A car can never pass the car in front of it. If it catches up, it slows down and drives right behind it at the slower speed. Cars driving together like this form a fleet. A single car on its own also counts as a fleet.

If a car catches up with a fleet exactly at the destination, it still counts as part of that fleet.

Return how many fleets arrive at the destination.

Input

An integer target, and two integer arrays position and speed of length n. All positions are different.

Output

The number of car fleets that reach target.

Example 1

Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]

Output: 3

The cars at 10 and 8 both need 1 hour, so they meet exactly at 12: one fleet. The car at 3 (3 hours) catches the car at 5 (7 hours): one fleet arriving at 7 hours. The car at 0 needs 12 hours and catches nobody.

Example 2

Input: target = 10, position = [3], speed = [3]

Output: 1

One car is one fleet.

Example 3

Input: target = 100, position = [0, 2, 4], speed = [4, 2, 1]

Output: 1

The car at 4 needs 96 hours. The others would be faster alone (25 and 49 hours), so they catch up and all arrive together.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“can never pass the car in front”

→ Only cars ahead matter → sort by position and process from the front.

“position and speed”

→ Collapse each car into one number: its time to reach the target.

“catches up … drives at the slower speed”

→ A car joins the fleet ahead if its time ≤ that fleet's time; otherwise it is a new, slower fleet.

Approach Complexity Ladder

Brute Force — check every car aheadO(N²)O(N)

A car leads its own fleet only if no car ahead arrives at the same time or later

Optimal — sort by position, stack of fleet timesO(N log N)O(N)

Sort front-to-back; push a car's time only if it is slower than the fleet ahead

Brute Force Intuition

Compute each car's time to the target if it drove alone. A car ends up behind someone if any car in front of it would arrive no earlier: it catches that car at or before the target. So count the cars for which no car ahead has time ≥ their time. Each such car leads its own fleet.

Recognition rule for this sub-pattern:

Need the first bigger value to the right (or left). Keep a decreasing stack; a bigger arrival resolves everyone smaller.

Remember this · Monotonic Stack

Trigger

Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"

Think

When a new element arrives, which older elements can never be the answer again?

Key question

Is my stack increasing or decreasing, and what do I record when I pop?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Next Greater Element II (circular)