Leetcode 475 Heaters

Leetcode 475 Heaters

https://leetcode.com/problems/heaters/description

This is a very interesting problem because it has a couple of train of thoughts for the solution.

First let’s take a look at the assumptions, looks like the heaters and houses are not guaranteed to be sorted arrays. But let’s assume for now that they are sorted. There are a couple of observations:

• For each house, if we want the minimum radius, it has to get heat from the nearest heater.
• Once we have the minimum distance from a heater for all the houses, we should get the max value to make sure all the houses are covered.

Now let’s step back to the original problem where heaters and houses are NOT sorted. What if we sort one of them? Let’s say heaters. Then the problem becomes this: give a house in the houses array, find where it will fit in the heaters array which is sorted. Sounds like we can use binary search! Once we have the position of the house in the heaters array, we can easily calculate the minimum distance for that house.

Now let’s take a look at the solution

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {

    heaters.sort((a, b) => a - b);
    console.log(heaters)

    const getMinimumDistanceFromHeater = (house) => {
        let left = 0;
        let right = heaters.length - 1;
        while(left + 1 < right) {
            let mid = Math.floor((left + right) / 2);
            if(heaters[mid] < house) {
                left = mid
            } else {
                right = mid
            }
        }

        let leftDistance = Math.abs(heaters[left] - house);
        let rightDistance = Math.abs(heaters[right] - house);
        return Math.min(leftDistance, rightDistance)
    }

    let result = 0;
    for(let i = 0; i < houses.length; i++) {
        const minDistance = getMinimumDistanceFromHeater(houses[i]);
        result = Math.max(minDistance, result)
    }

    return result;
};

The time complexity is O(mLogn + nLogn) where m is the length of the houses array and n is the length of heaters array.

What if we sort both arrays?

We can use two pointers for each array to solve this problem. What we do is basically decide for each house, which heater it should get heat from? Should it be the current heater OR the next heater(if it’s there)?

• If the current heater wins, we move on to the next house
• If the next heater wins, we move the pointer for the heaters to the next one.
• Until both the houses and heaters array are done.
• Along the way, we also need to update the final result accordingly.

Code:

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {
    houses.sort((a, b) => a - b)
    heaters.sort((a, b) => a - b)
    let heaterIndex = 0;
    let houseIndex = 0;
    let result = 0;
    while(houseIndex < houses.length && heaterIndex < heaters.length) {
        const distanceToCurrentHeater = Math.abs(heaters[heaterIndex] - houses[houseIndex]);
        let distanceToNextHeater = Infinity;
        if(heaterIndex < heaters.length - 1) {
            distanceToNextHeater = Math.abs(heaters[heaterIndex + 1] - houses[houseIndex]);
        }

        if(distanceToCurrentHeater < distanceToNextHeater) {
            houseIndex++;
            result = Math.max(result, distanceToCurrentHeater)
        } else {
            heaterIndex++;
        }
    }

    return result
};

The time complexity mainly comes from the sorting part of the 2 arrays(O(nLogn)), after that each array will be iterated once so the final time complexity is O(nLogn + mLogm)) where m and n are the length of the arrays respectively.