Car Fleet II LeetCode solution in Java

1
class Solution {
2
  public double[] getCollisionTimes(int[][] cars) {
3
    int n = cars.length;
4
    double[] res = new double[n];
5
    Arrays.fill(res, -1.0);
6

7
    // as soon as a car c1 catches another car c2, we can say c1 vanishes into c2; meaning that
8
    // after catching c2, we may view c1 as non-existing (cars before c1 may not catches c1);
9

10
    /**
11
     * Define a stack storing the index of cars as follows:
12
     *
13
     * <p>Assuming cars c_0, c_1, c_2, ... , c_k are in the stack, they satisfy: 1. v0 > v1 > v2 ...
14
     * > vk where v_i is the velocity of car c_i 2. c_(i+1) is the car that c_i vanishes into
15
     *
16
     * <p>Namely, if only these cars exist, then what will happened is that c_0 vanishes into c_1,
17
     * then c_1 vanishes into c_2, ..., c_(k-1) vanishes into c_k;
18
     */
19
    Deque<Integer> stack = new LinkedList<>();
20
    for (int i = n - 1; i >= 0; i--) {
21
      int[] c1 = cars[i];
22
      while (!stack.isEmpty()) {
23
        int j = stack.peekLast();
24
        int[] c2 = cars[j];
25

26
        /**
27
         * If both conditions are satisfied: 1. c1 is faster than c2 2. c1 catches c2 before c2
28
         * vanishes into other car
29
         *
30
         * <p>Then we know that c2 is the car that c1 catches first (i.e., c1 vanishes into c2) ==>
31
         * get the result for c1
32
         *
33
         * <p>Note neither c1 nor c2 is polled out from the stack considering the rule of stack.
34
         */
35
        if (c1[1] > c2[1] && (res[j] == -1.0 || catchTime(cars, i, j) <= res[j])) {
36
          res[i] = catchTime(cars, i, j);
37
          break;
38
        }
39

40
        /**
41
         * Now we have either one of situations 1. c1 is slower than c2 2. c1 potentially catches c2
42
         * AFTER c2 vanishes
43
         *
44
         * <p>Claim: no car before c1 will vanish into c2
45
         *
46
         * <p>1. ==> cars before c1 will vanish into c1 first before catching c2 2. <==> c2
47
         * "vanishes" into another car even before c1 catches it
48
         *
49
         * <p>Either way, c2 can not be catched by c1 or cars beofre c1 ==> poll it out from stack
50
         */
51
        stack.pollLast();
52
      }
53
      stack.offerLast(i);
54
    }
55
    return res;
56
  }
57

58
  // time for cars[i] to catch cars[j]
59
  private double catchTime(int[][] cars, int i, int j) {
60
    int dist = cars[j][0] - cars[i][0];
61
    int v = cars[i][1] - cars[j][1];
62

63
    return (double) dist / v;
64
  }
65
}