Heaters

Medium

Anduril

1 view

Topics:

ArraysBinary SearchTwo Pointers

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range.

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Notice that all the heaters follow your radius standard, and the warm radius will the same.

Example 1:

Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.

Example 3:

Input: houses = [1,5], heaters = [2]
Output: 3

Constraints:

1 <= houses.length, heaters.length <= 3 * 10⁴
1 <= houses[i], heaters[i] <= 10⁹

Try coding it in LeetCode

Heaters

Medium

Anduril

1 view

Topics:

ArraysBinary SearchTwo Pointers

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range.

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Notice that all the heaters follow your radius standard, and the warm radius will the same.

Example 1:

Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.

Example 3:

Input: houses = [1,5], heaters = [2]
Output: 3

Constraints:

1 <= houses.length, heaters.length <= 3 * 10⁴
1 <= houses[i], heaters[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the house and heater positions? Are they bounded?
Can the `houses` and `heaters` arrays be empty, or contain null values?
If a house's position is the same as a heater's position, does it need any additional radius coverage?
If no radius can cover all houses, what should I return?
Are the house and heater positions guaranteed to be distinct, or can there be duplicates?

Brute Force Solution

Approach

Imagine you have houses along a line and you need to find the smallest radius of heaters to warm all the houses. The brute force approach is like trying every possible radius, one by one, to see if it covers all the houses. We check each house for each radius to see if it's warmed.

Here's how the algorithm would work step-by-step:

Start with a really small radius, like zero.
Go through each house and check if there's a heater close enough to warm it within that radius.
If even one house is not warmed by any heater, that radius is too small.
Increase the radius by a little bit.
Repeat the process of checking every house with this new, slightly bigger radius.
Keep increasing the radius until you find a radius where *every* single house is warmed by at least one heater.
That radius is the smallest possible radius that warms all the houses.

Code Implementation

def find_smallest_heater_radius_brute_force(houses, heaters):
    radius = 0
    while True:
        house_is_warmed_by_heaters = True

        # Check if every house is warmed by at least one heater with the current radius
        for house in houses:
            house_is_warmed = False
            for heater in heaters:
                if abs(house - heater) <= radius:
                    house_is_warmed = True
                    break

            if not house_is_warmed:
                house_is_warmed_by_heaters = False
                break

        # If all houses are warmed, return the current radius
        if house_is_warmed_by_heaters:
            return radius

        # Increment the radius and try again
        radius += 1

Big(O) Analysis

Time Complexity

O(n*m) – The brute force solution iterates through possible radius values until a suitable radius is found. For each radius, we iterate through all the n houses to check if they are covered by any of the m heaters. This involves checking each house against each heater for every possible radius until all houses are covered. Therefore, in the worst case, the time complexity is proportional to n * m, assuming the radius increment is sufficiently small to require multiple iterations.

Space Complexity

O(1) – The provided brute force approach doesn't use any auxiliary data structures like lists, sets, or hashmaps to store intermediate results. It only involves iterating through houses and heaters and comparing distances. The algorithm only uses a few variables to store the radius and boolean flags to indicate if a house is heated, which takes constant space regardless of the number of houses (N). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the minimum radius each heater needs to cover all houses. We will leverage the sorted nature of both houses and heaters to efficiently determine the closest heater for each house, optimizing the search process.

Here's how the algorithm would work step-by-step:

First, make sure the heaters are in increasing order.
For each house, find the closest heater. This is done by finding the heater that's just before the house's location and the one just after.
Calculate the distance from the house to both of those heaters.
Pick the smaller of those two distances. That's how far away the closest heater is for that house.
Keep track of the biggest of all the 'closest heater' distances that you found for all the houses.
That largest distance is the minimum radius the heaters need to cover all the houses.

Code Implementation

def findRadius(houses, heaters):
    heaters.sort()
    maximum_radius = 0

    for house_position in houses:
        # Need to find closest heater for each house.
        left_heater_index = 0
        right_heater_index = len(heaters) - 1

        while left_heater_index < right_heater_index:
            middle_heater_index = (left_heater_index + right_heater_index) // 2
            if heaters[middle_heater_index] < house_position:
                left_heater_index = middle_heater_index + 1
            else:
                right_heater_index = middle_heater_index

        # Binary search gives us the index of the heater >= house
        closest_right_heater_distance = float('inf')
        if left_heater_index < len(heaters):
            closest_right_heater_distance = heaters[left_heater_index] - house_position

        closest_left_heater_distance = float('inf')
        if left_heater_index > 0:
            closest_left_heater_distance = house_position - heaters[left_heater_index - 1]

        # Determining the closest heater
        minimum_heater_distance = min(closest_left_heater_distance, closest_right_heater_distance)
        maximum_radius = max(maximum_radius, minimum_heater_distance)

    return maximum_radius

Big(O) Analysis

Time Complexity

O(n log m) – The solution first sorts the heaters, which takes O(m log m) time, where m is the number of heaters. Then, for each of the n houses, we perform a binary search (log m) to find the two nearest heaters. Since we iterate through all n houses, this step takes O(n log m) time. Since m log m will be less than n log m in most cases, the overall time complexity is dominated by the iteration through the houses and the binary search for the nearest heaters. Thus, the overall runtime complexity is O(n log m).

Space Complexity

O(1) – The algorithm primarily uses a few constant space variables for iteration and distance calculation. It sorts the heaters array in place, which depending on the sorting algorithm used may or may not take extra space; assuming an in-place sort like heapsort or insertion sort, no significant auxiliary space is required for that either. Therefore, the space used does not scale with the input size of houses or heaters, remaining constant. Hence, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty houses array	Return 0 as no houses need heating when the houses array is empty.
Empty heaters array	Return infinity as no houses can be heated if there are no heaters.
Single house and single heater	Return the absolute difference between their positions.
All houses are located at the same position	Find the minimum distance to the nearest heater for that specific location.
All heaters are located at the same position	Find the maximum of the minimum distances between each house and that heater position.
Houses and heaters are already sorted	The algorithm should still work efficiently, potentially optimizing early exits.
Houses are located far away from heaters (potential integer overflow)	Use long integers for calculations to avoid potential integer overflow problems when calculating distances.
Extremely large number of houses and heaters (scaling issues)	Ensure the algorithm's time complexity is optimized, ideally O(n log m), where n is houses and m is heaters, using binary search.