Car Fleet II Solution in Python

Explore More Solutions:

Problem Description

Welcome to the world of traffic jams and impatient drivers! Imagine you’re on a highway, and you see a line of cars ahead of you. Each car is moving at its own speed, and some are slower than others. Now, if you were to think about it, wouldn’t it be hilarious if these cars could just magically collide and form fleets? Well, that’s exactly what the Car Fleet II problem is about!

In this LeetCode challenge, you’re tasked with figuring out when these cars will collide based on their positions and speeds. Think of it as a game of bumper cars, but with a twist: some cars are just too slow to keep up, and they might never collide with the faster ones. So, how do you determine the collision times? Spoiler alert: it involves a bit of math and some clever thinking!

Code Solution


class Solution:
    def getCollisionTimes(self, cars: list[list[int]]) -> list[float]:
        ans = []
        stack = []  # (pos, speed, collisionTime)

        def getCollisionTime(car: tuple[int, int, int], pos: int, speed: int) -> float:
            return (car[0] - pos) / (speed - car[1])

        for pos, speed in reversed(cars):
            while stack and (speed <= stack[-1][1] or getCollisionTime(stack[-1], pos, speed) >= stack[-1][2]):
                stack.pop()
            if stack:
                collisionTime = getCollisionTime(stack[-1], pos, speed)
                stack.append((pos, speed, collisionTime))
                ans.append(collisionTime)
            else:
                stack.append((pos, speed, math.inf))
                ans.append(-1)

        return ans[::-1]

Approach Explanation

The code uses a stack to keep track of the cars and their collision times. By iterating through the cars in reverse order, it checks if the current car can collide with the one in front of it. If the current car is slower or if the calculated collision time is greater than the time of the car in front, it pops the stack. If a collision is possible, it calculates the collision time and adds it to the stack. If no collision is possible, it appends -1 to indicate that the car will never collide.

Time and Space Complexity

Time Complexity: O(n), where n is the number of cars. Each car is processed once.
Space Complexity: O(n) in the worst case, where all cars are stored in the stack.

Real-World Example

Imagine you’re at a traffic light, and the light turns green. The car in front of you is a slowpoke, and you’re itching to zoom ahead. But wait! If you were to collide with that car, it would be a disaster. This scenario mirrors the Car Fleet II problem, where you need to calculate when (or if) you’ll collide with the car ahead based on your speed and position.