Problem

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.

Examples

Example 1

1
2
3

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

1
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 <= positioni, speedi <= 10^6
  • positioni < positioni+1

Solution

Method 1 – Monotonic Stack (Reverse Traversal)

Intuition

We process cars from right to left, using a stack to keep track of possible collision candidates. For each car, we compute the time it would take to collide with the car ahead. If the car ahead will collide with another car before our current car can catch up, we skip it. This ensures we only consider valid collision times.

Approach

  1. Initialize an empty stack to store indices of cars that are possible collision candidates.
  2. Iterate from the last car to the first:
    • While the stack is not empty:
      • If the current car cannot catch up to the car at the top of the stack, pop the stack.
      • Else, compute the collision time.
      • If the car at the top of the stack will collide with another car before our current car can catch up, pop the stack.
      • Otherwise, break.
    • If the stack is not empty, set the collision time for the current car.
    • Push the current car index onto the stack.
  3. Return the collision times array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        int n = cars.size();
        vector<double> ans(n, -1.0);
        stack<int> st;
        for (int i = n - 1; i >= 0; --i) {
            int p = cars[i][0], s = cars[i][1];
            while (!st.empty()) {
                int j = st.top();
                int pj = cars[j][0], sj = cars[j][1];
                if (s <= sj) {
                    st.pop();
                } else {
                    double t = (pj - p) * 1.0 / (s - sj);
                    if (ans[j] < 0 || t <= ans[j]) {
                        ans[i] = t;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }
            st.push(i);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func getCollisionTimes(cars [][]int) []float64 {
    n := len(cars)
    ans := make([]float64, n)
    for i := range ans {
        ans[i] = -1
    }
    st := []int{}
    for i := n - 1; i >= 0; i-- {
        p, s := cars[i][0], cars[i][1]
        for len(st) > 0 {
            j := st[len(st)-1]
            pj, sj := cars[j][0], cars[j][1]
            if s <= sj {
                st = st[:len(st)-1]
            } else {
                t := float64(pj-p) / float64(s-sj)
                if ans[j] < 0 || t <= ans[j] {
                    ans[i] = t
                    break
                } else {
                    st = st[:len(st)-1]
                }
            }
        }
        st = append(st, i)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public double[] getCollisionTimes(int[][] cars) {
        int n = cars.length;
        double[] ans = new double[n];
        Arrays.fill(ans, -1.0);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            int p = cars[i][0], s = cars[i][1];
            while (!st.isEmpty()) {
                int j = st.peek();
                int pj = cars[j][0], sj = cars[j][1];
                if (s <= sj) {
                    st.pop();
                } else {
                    double t = (pj - p) * 1.0 / (s - sj);
                    if (ans[j] < 0 || t <= ans[j]) {
                        ans[i] = t;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }
            st.push(i);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun getCollisionTimes(cars: Array<IntArray>): DoubleArray {
        val n = cars.size
        val ans = DoubleArray(n) { -1.0 }
        val st = ArrayDeque<Int>()
        for (i in n - 1 downTo 0) {
            val (p, s) = cars[i]
            while (st.isNotEmpty()) {
                val j = st.last()
                val (pj, sj) = cars[j]
                if (s <= sj) {
                    st.removeLast()
                } else {
                    val t = (pj - p).toDouble() / (s - sj)
                    if (ans[j] < 0 || t <= ans[j]) {
                        ans[i] = t
                        break
                    } else {
                        st.removeLast()
                    }
                }
            }
            st.addLast(i)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def getCollisionTimes(self, cars: list[list[int]]) -> list[float]:
        n = len(cars)
        ans = [-1.0] * n
        st = []
        for i in range(n - 1, -1, -1):
            p, s = cars[i]
            while st:
                j = st[-1]
                pj, sj = cars[j]
                if s <= sj:
                    st.pop()
                else:
                    t = (pj - p) / (s - sj)
                    if ans[j] < 0 or t <= ans[j]:
                        ans[i] = t
                        break
                    else:
                        st.pop()
            st.append(i)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn get_collision_times(cars: Vec<Vec<i32>>) -> Vec<f64> {
        let n = cars.len();
        let mut ans = vec![-1.0; n];
        let mut st = Vec::new();
        for i in (0..n).rev() {
            let (p, s) = (cars[i][0], cars[i][1]);
            while let Some(&j) = st.last() {
                let (pj, sj) = (cars[j][0], cars[j][1]);
                if s <= sj {
                    st.pop();
                } else {
                    let t = (pj - p) as f64 / (s - sj) as f64;
                    if ans[j] < 0.0 || t <= ans[j] {
                        ans[i] = t;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }
            st.push(i);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    getCollisionTimes(cars: number[][]): number[] {
        const n = cars.length;
        const ans = Array(n).fill(-1.0);
        const st: number[] = [];
        for (let i = n - 1; i >= 0; i--) {
            const [p, s] = cars[i];
            while (st.length) {
                const j = st[st.length - 1];
                const [pj, sj] = cars[j];
                if (s <= sj) {
                    st.pop();
                } else {
                    const t = (pj - p) / (s - sj);
                    if (ans[j] < 0 || t <= ans[j]) {
                        ans[i] = t;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }
            st.push(i);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)