leetcode-javascript/solutions/0475-heaters.js at development · Anuj9826/leetcode-javascript · 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
/**
 * Heaters
 * Time Complexity: O(N log N + M log M + N log M)
 * Space Complexity: O(1)
 */
var findRadius = function (houseCoordinates, heaterPositions) {
    houseCoordinates.sort((firstElement, secondElement) => firstElement - secondElement);
    heaterPositions.sort((firstElement, secondElement) => firstElement - secondElement);

    let overallMinimumRadius = 0;

    for (const currentHouseCoordinate of houseCoordinates) {
        let leftBoundary = 0;
        let rightBoundary = heaterPositions.length - 1;
        let minimumDistanceForHouse = Number.POSITIVE_INFINITY;

        while (leftBoundary <= rightBoundary) {
            let middlePoint = Math.floor((leftBoundary + rightBoundary) / 2);
            let currentHeaterCoordinate = heaterPositions[middlePoint];

            minimumDistanceForHouse = Math.min(minimumDistanceForHouse, Math.abs(currentHouseCoordinate - currentHeaterCoordinate));

            if (currentHeaterCoordinate < currentHouseCoordinate) {
                leftBoundary = middlePoint + 1;
            } else if (currentHeaterCoordinate > currentHouseCoordinate) {
                rightBoundary = middlePoint - 1;
            } else {
                minimumDistanceForHouse = 0;
                break;
            }
        }
        overallMinimumRadius = Math.max(overallMinimumRadius, minimumDistanceForHouse);
    }

    return overallMinimumRadius;
};