leetcode/javascript/0853-car-fleet.js at main · neetcode-gh/leetcode · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * https://leetcode.com/problems/car-fleet
 * Time O(N * log(N)) | Space O(N)
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
var carFleet = function (target, position, speed) {
    const coordinates = getCoordinates(
        target,
        position,
        speed,
    ); /* Time O(N * log(N)) | Space O(N) */

    return searchAscending(coordinates); /* Time O(N)          | Space O(N) */
};

var getCoordinates = (target, position, speed) =>
    position
        .map((_position, index) => [
            _position,
            speed[index],
        ]) /* Time O(N)          | Space O(N) */
        .sort(
            ([aPosition], [bPosition]) => aPosition - bPosition,
        ) /* Time O(N * log(N)) | HeapSort Space 0(1) | QuickSort Space O(log(N)) */
        .map(
            ([_position, _speed]) => (target - _position) / _speed,
        ); /* Time O(N)          | Space O(N) */

var searchAscending = (coordinates, stack = []) => {
    for (const coordinate of coordinates) {
        /* Time O(N + N) */
        shrink(coordinate, stack); /* Time O(N + N) */
        stack.push(coordinate); /* Space O(N) */
    }

    return stack.length;
};

const shrink = (coordinate, stack) => {
    const isPreviousLess = () => stack[stack.length - 1] <= coordinate;
    while (stack.length && isPreviousLess()) stack.pop(); /* Time O(N + N) */
};

/**
 * https://leetcode.com/problems/car-fleet
 * Time O(N * log(N)) | Space O(N)
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
var carFleet = function (target, position, speed) {
    const coordinates = getCoordinates(
        target,
        position,
        speed,
    ); /* Time O(N * log(N)) | Space O(N) */

    return searchDescending(coordinates); /* Time O(N) */
};

var getCoordinates = (target, position, speed) =>
    position
        .map((_position, index) => [
            _position,
            speed[index],
        ]) /* Time O(N)          | Space O(N) */
        .sort(
            ([aPosition], [bPosition]) => bPosition - aPosition,
        ) /* Time O(N * log(N)) | HeapSort Space 0(1) | QuickSort Space O(log(N)) */
        .map(
            ([_position, _speed]) => (target - _position) / _speed,
        ); /* Time O(N)          | Space O(N) */

var searchDescending = (coordinates, previous = 0, fleets = 0) => {
    for (const coordinate of coordinates) {
        /* Time O(N) */
        const isPreviousLess = previous < coordinate;
        if (!isPreviousLess) continue;

        previous = coordinate;
        fleets++;
    }

    return fleets;
};