View Problem on Leetcode

Problem Description

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer array 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 car or 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.

Approach

  1. Create a list of tuples (position, time to reach target) for each car.
  2. Sort the list in descending order of position.
  3. Iterate through the sorted list, keeping track of the slowest time seen so far.
  4. If a car takes longer to reach the target than the current slowest time, it forms a new fleet.
  5. Count the number of fleets and return the result.

Visualization

Car Fleet Visualization

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        stack = []

        for pos, speed in cars:
            time = (target - pos) / speed

            if not stack or time > stack[-1]:
                stack.append(time)

        return len(stack)