#1776

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Car Fleet II

Car Fleet II involves calculating collision times between cars traveling at different speeds along a one-lane road using stack-based state management.

array math stack heap priority queue monotonic stack

Problem Statement

You are given an array of n cars, where each car is represented by a pair of integers: the car’s position and speed. These cars are all traveling along the same one-lane road in the same direction. The problem asks you to calculate the time it will take for each car to collide with the next car or determine if they won’t collide. Cars that collide will form a fleet, and all cars in that fleet will travel at the speed of the slowest car in the fleet.

The goal is to return an array where each element corresponds to the time it will take for the ith car to collide with the next one. If a car never collides, the corresponding value should be -1. You should be able to assume that once cars merge into a fleet, they won’t separate, and all of them will travel at the same speed as the slowest car.

Examples

Example 1

Input: cars = [[1,2],[2,1],[4,3],[7,2]]

Output: [1.00000,-1.00000,3.00000,-1.00000]

After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.

Example 2

Input: cars = [[3,4],[5,4],[6,3],[9,1]]

Output: [2.00000,1.00000,1.50000,-1.00000]

Example details omitted.

Constraints

1 <= cars.length <= 105
1 <= positioni, speedi <= 106
positioni < positioni+1

Solution Approach

Stack-based Approach

Use a stack to simulate the movement of the cars. The stack stores the time required for a car to catch up with the previous car in the array. By processing cars from the back to the front, we calculate the time each car will collide with the next one or if it won't. If a car reaches another car, both will join into a fleet, and the slowest speed will determine their new velocity.

Mathematical Formula for Time Calculation

For each car, the time to collide with the next car is determined by the relative position and the difference in speeds. The time is calculated using the formula: time = (position[i+1] - position[i]) / (speed[i] - speed[i+1]). If the speed of the current car is greater than the next car, the current car will never catch up, and the time is -1.

Efficient Simulation

To optimize, we process the cars in reverse order and track the fleet formation using a stack. This ensures that only relevant collisions are considered, and unnecessary checks are avoided, making the approach both time-efficient and space-efficient. We do not simulate the merging of fleets directly; instead, we rely on the stack to handle state management efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of cars. This is due to the single pass over the cars and the stack operations, which are all O(1). The space complexity is O(n), as we store each car’s time in the stack.

What Interviewers Usually Probe

Understanding the stack-based state management is key to solving this problem.
Candidates should demonstrate familiarity with simulating car fleets efficiently.
Be aware of the subtle handling of edge cases such as cars not colliding.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the case where a car’s speed is greater than the next car’s speed, resulting in no collision.
Incorrectly merging fleets or failing to track fleet speeds properly.
Forgetting to handle the case where no collision happens (returning -1).

Follow-up variants

What if the cars were moving in different directions?
How would the problem change if you were asked to track the position of each car over time?
What if there were additional constraints like fuel limits on each car?

FAQ

What is the primary pattern to use for solving Car Fleet II?

The primary pattern is stack-based state management, which helps simulate the merging of car fleets and calculating collision times efficiently.

What if a car does not collide with another car in Car Fleet II?

If a car does not collide, the corresponding time is set to -1 in the answer array.

How do you calculate the time for a car to collide with the next one in Car Fleet II?

You calculate the time using the formula: time = (position[i+1] - position[i]) / (speed[i] - speed[i+1]). If the speed of the current car is greater than the next car, there will be no collision.

Why is the stack-based approach important for solving Car Fleet II?

The stack-based approach allows for efficient simulation of the fleet formation process, ensuring we handle merging cars correctly and avoid unnecessary calculations.

How does GhostInterview assist in solving Car Fleet II?

GhostInterview helps by providing step-by-step guidance on implementing a stack-based solution and ensuring you efficiently manage the cars' collision times.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        stk = []
        n = len(cars)
        ans = [-1] * n
        for i in range(n - 1, -1, -1):
            while stk:
                j = stk[-1]
                if cars[i][1] > cars[j][1]:
                    t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])
                    if ans[j] == -1 or t <= ans[j]:
                        ans[i] = t
                        break
                stk.pop()
            stk.append(i)
        return ans

Continue Practicing

#2454 next greater element iv #2617 minimum number of visited cells in a grid #1793 maximum score of a good subarray