1776. Car Fleet II LeetCode Solution

In this guide, you will get 1776. Car Fleet II LeetCode Solution with the best time and space complexity. The solution to Car Fleet II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Car Fleet II solution in C++
Car Fleet II solution in Java
Car Fleet II solution in Python
Additional Resources

1776. Car Fleet II LeetCode Solution image

Problem Statement of Car Fleet II

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [positioni, speedi] represents:

positioni is the distance between the ith car and the beginning of the road in meters. It is guaranteed that positioni < positioni+1.
speedi is the initial speed of the ith car in meters per second.

For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.
Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10-5 of the actual answers are accepted.

Example 1:

Input: cars = [[1,2],[2,1],[4,3],[7,2]]
Output: [1.00000,-1.00000,3.00000,-1.00000]
Explanation: 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]

Constraints:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1776. Car Fleet II LeetCode Solution in C++

struct Car {
  int pos;
  int speed;
  double collisionTime;
  Car(int pos, int speed, double collisionTime)
      : pos(pos), speed(speed), collisionTime(collisionTime) {}
};

class Solution {
 public:
  vector<double> getCollisionTimes(vector<vector<int>>& cars) {
    vector<double> ans(cars.size());
    stack<Car> stack;

    for (int i = cars.size() - 1; i >= 0; --i) {
      const int pos = cars[i][0];
      const int speed = cars[i][1];
      while (!stack.empty() && (speed <= stack.top().speed ||
                                getCollisionTime(stack.top(), pos, speed) >=
                                    stack.top().collisionTime))
        stack.pop();
      if (stack.empty()) {
        stack.emplace(pos, speed, INT_MAX);
        ans[i] = -1;
      } else {
        const double collisionTime = getCollisionTime(stack.top(), pos, speed);
        stack.emplace(pos, speed, collisionTime);
        ans[i] = collisionTime;
      }
    }

    return ans;
  }

 private:
  double getCollisionTime(const Car& car, int pos, int speed) {
    return (car.pos - pos) / (double)(speed - car.speed);
  }
};
/* code provided by PROGIEZ */

1776. Car Fleet II LeetCode Solution in Java

class Solution {
  public double[] getCollisionTimes(int[][] cars) {
    double[] ans = new double[cars.length];
    Deque<Car> stack = new ArrayDeque<>();

    for (int i = cars.length - 1; i >= 0; --i) {
      final int pos = cars[i][0];
      final int speed = cars[i][1];
      while (!stack.isEmpty() &&
             (speed <= stack.peek().speed ||
              getCollisionTime(stack.peek(), pos, speed) >= stack.peek().collisionTime))
        stack.pop();
      if (stack.isEmpty()) {
        stack.push(new Car(pos, speed, Integer.MAX_VALUE));
        ans[i] = -1;
      } else {
        final double collisionTime = getCollisionTime(stack.peek(), pos, speed);
        stack.push(new Car(pos, speed, collisionTime));
        ans[i] = collisionTime;
      }
    }

    return ans;
  }

  private record Car(int pos, int speed, double collisionTime) {}

  private double getCollisionTime(Car car, int pos, int speed) {
    return (double) (car.pos - pos) / (speed - car.speed);
  }
}
// code provided by PROGIEZ

1776. Car Fleet II LeetCode Solution in Python

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]
 # code by PROGIEZ