Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1776.html

1776. Car Fleet II

Level

Hard

Description

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] = [position_i, speed_i] represents:

• position_i is the distance between the i-th car and the beginning of the road in meters. It is guaranteed that position_i < position_(i+1).
• speed_i is the initial speed of the i-th 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 i-th 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 <= 10^5
• 1 <= position_i, speed_i <= 10^6
• position_i < position_(i+1)

Solution

For each car, only the cars before the current car need to be considered. Loop over cars backwards and use monotonic stack, where the bottom element is the lowest car. For each car, if the top element in the stack is slower, then the current car will collide with the car at the top of the stack, and calculate the time that the collision happens.

• Java
• Python
• C++
• Go

• class Solution {
      public double[] getCollisionTimes(int[][] cars) {
          int length = cars.length;
          double[] times = new double[length];
          Deque<Integer> stack = new LinkedList<Integer>();
          for (int i = length - 1; i >= 0; i--) {
              while (!stack.isEmpty()) {
                  if (cars[stack.peek()][1] >= cars[i][1])
                      stack.pop();
                  else {
                      if (times[stack.peek()] < 0)
                          break;
                      double time = times[stack.peek()] * (cars[i][1] - cars[stack.peek()][1]);
                      if (time > cars[stack.peek()][0] - cars[i][0])
                          break;
                      else
                          stack.pop();
                  }
              }
              if (stack.isEmpty())
                  times[i] = -1;
              else
                  times[i] = (double) (cars[stack.peek()][0] - cars[i][0]) / (cars[i][1] - cars[stack.peek()][1]);
              stack.push(i);
          }
          return times;
      }
  }
  
  ############
  
  class Solution {
      public double[] getCollisionTimes(int[][] cars) {
          int n = cars.length;
          double[] ans = new double[n];
          Arrays.fill(ans, -1.0);
          Deque<Integer> stk = new ArrayDeque<>();
          for (int i = n - 1; i >= 0; --i) {
              while (!stk.isEmpty()) {
                  int j = stk.peek();
                  if (cars[i][1] > cars[j][1]) {
                      double t = (cars[j][0] - cars[i][0]) * 1.0 / (cars[i][1] - cars[j][1]);
                      if (ans[j] < 0 || t <= ans[j]) {
                          ans[i] = t;
                          break;
                      }
                  }
                  stk.pop();
              }
              stk.push(i);
          }
          return ans;
      }
  }
  

• 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
  
  
  

• class Solution {
  public:
      vector<double> getCollisionTimes(vector<vector<int>>& cars) {
          int n = cars.size();
          vector<double> ans(n, -1.0);
          stack<int> stk;
          for (int i = n - 1; ~i; --i) {
              while (stk.size()) {
                  int j = stk.top();
                  if (cars[i][1] > cars[j][1]) {
                      double t = (cars[j][0] - cars[i][0]) * 1.0 / (cars[i][1] - cars[j][1]);
                      if (ans[j] < 0 || t <= ans[j]) {
                          ans[i] = t;
                          break;
                      }
                  }
                  stk.pop();
              }
              stk.push(i);
          }
          return ans;
      }
  };
  

• func getCollisionTimes(cars [][]int) []float64 {
  	n := len(cars)
  	ans := make([]float64, n)
  	for i := range ans {
  		ans[i] = -1.0
  	}
  	stk := []int{}
  	for i := n - 1; i >= 0; i-- {
  		for len(stk) > 0 {
  			j := stk[len(stk)-1]
  			if cars[i][1] > cars[j][1] {
  				t := float64(cars[j][0]-cars[i][0]) / float64(cars[i][1]-cars[j][1])
  				if ans[j] < 0 || t <= ans[j] {
  					ans[i] = t
  					break
  				}
  			}
  			stk = stk[:len(stk)-1]
  		}
  		stk = append(stk, i)
  	}
  	return ans
  }
  

All Problems

All Solutions