475. Heaters

MediumArrayTwo PointersBinary SearchSorting
Leetcode Link

Problem Description

In this problem, we're given two arrays: houses and heaters. Each element in the houses array represents the position of a house on a horizontal line, and each element in the heaters array represents the position of a heater on the same line. Our objective is to find the minimum radius required for all the heaters so that every house can be covered by at least one heater's warm radius. Keep in mind that all heaters are set to the same radius, and we must choose it so every house is within the radius of at least one heater.

The goal is to minimize this radius while still ensuring that every house is within the warm range of at least one heater.

Intuition

Intuitively, we can think of this as a form of the binary search problem. We want to find the smallest radius such that every house is warm, meaning it falls within the range of [heater position - radius, heater position + radius] for at least one heater. To do this, we start by sorting both the houses and heaters arrays to simplify the process of checking if a house is within the warm radius of a heater.

The key insight behind the solution is to use binary search to find the minimum required radius. The binary search space is from 0 to the maximum possible distance between a house and a heater, which we initially assume to be a large number (like 10^9). We define a function check that, given a radius value r, determines whether all houses can be warmed with the heaters set to the specified radius.

Our binary search works as follows:

  1. We set left to 0 and right to a large number, defining our initial search space for the radius.
  2. We enter a loop where we continually narrow down our search space:
    • We calculate the middle value mid between left and right.
    • We call the check function with this mid value to see if it's possible to cover all houses with this radius.
    • If check returns True, it means the radius mid is sufficient, and we might be able to find a smaller radius that also works. So we set right to mid to look for a potentially smaller valid radius.
    • If check returns False, it means the radius mid is not enough to cover all houses, so we need a larger radius. We set left to mid + 1 to search for a larger valid radius.
  3. When left is equal to right, we have found the smallest radius that can cover all the houses.

The check function works by iterating through each house and determining if it's within the warm radius of at least one heater.

Once we exit the binary search loop, left will hold the minimum radius needed so that all houses are within the range of at least one heater.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What are the most two important steps in writing a depth first search function? (Select 2)

Solution Approach

The solution leverages the binary search algorithm to zero in on the smallest possible radius. Here are the details of the implementation steps, referencing the provided solution code:

  1. Sorting Input Arrays: The problem starts with sorting both houses and heaters arrays. Sorting is crucial because it allows the check function to iterate over houses and heaters in order, efficiently determining if each house is covered by the current radius.

  2. Binary Search Setup: To find the correct radius, the code sets up a binary search with left as 0 and right as int(1e9) โ€“ a large enough number to ensure it's greater than any potential radius needed.

  3. The check Function: This helper function checks whether a given radius r is sufficient to warm all houses. It initializes two pointers: i for houses and j for heaters. For each house, it checks if it falls in the range of the heater at index j. If not, it moves to the next heater and repeats the check. If all houses can be covered with the given radius, it returns True; otherwise, False.

  4. Using Binary Search:

    • A loop continues until left is not less than right, meaning the binary search space has been narrowed down to a single value.
    • We calculate a mid value as the average of left and right. This mid represents the potential minimum radius.
    • We call check(mid) to verify if all houses are warmed by heaters with radius mid.
      • If True, the mid radius is large enough, and we attempt to find a smaller minimum by setting right to mid.
      • If False, the mid radius is too small, so we look for a larger radius by setting left to mid + 1.

  5. Convergence and Result: By continuously halving the search space, the binary search converges to the minimum radius required, which is then returned by the function when left equals right. This is because when check(mid) can no longer find a radius that covers all houses, left will now point to the smallest valid radius found.

The main data structure used is the sorted arrays, which enable efficient traversal. The binary search algorithm is the core pattern used to minimize the heater radius, and the check function is an implementation of a two-pointer technique to match heaters to houses within a given warm radius. Combining sorting, binary search, and two-pointer techniques makes the solution efficient and enables it to handle a wide range of input sizes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example Walkthrough

Let's say we have the following array of houses: [1, 2, 3, 4], and heaters: [1, 4]. We want to use the solution approach to find the minimum heater radius.

  1. Sorting Input Arrays:

    • The houses array is already sorted: [1, 2, 3, 4].
    • The heaters array is already sorted: [1, 4].

  2. Binary Search Setup:

    • We set left to 0 and right to 10^9 (a very large number).

  3. Binary Search Start

    • The initial value of left is 0, and right is 10^9.

  4. Binary Search Iteration

    • First Iteration:
      • mid = (left + right) / 2 which calculates to (0 + 10^9) / 2 = 5 * 10^8.
      • We use check(5 * 10^8) which will definitely return True because the radius is very large and will cover all houses. We then set right to mid which now becomes 5 * 10^8.
    • Second Iteration:
      • Now we have left = 0, right = 5 * 10^8.
      • mid = (left + right) / 2 = 2.5 * 10^8.
      • Again, check(2.5 * 10^8) will return True. We update right to 2.5 * 10^8.
    • We keep iterating, and the value of right will continue to decrease until check returns False, which indicates the mid value is insufficient for a heater radius.

  5. Finding the Minimum Radius

    • We continue the binary search to narrow down the minimum radius that can cover all houses. Assuming our houses and heaters, a mid of 2 would be enough to cover all the houses (house at position 2 is at a distance of 2 from heater 1, and house at 3 is also at a distance of 1 from heater 4).
    • So, when the check function is called with mid values lower than 2, it will start to return False, prompting the binary search to stop decreasing the right boundary.

  6. Arriving at the Solution

    • The binary search algorithm will continue to narrow down until left and right converge, giving us the minimum radius needed.
    • For our example, after enough iterations, left will equal right at the value of 2. This means the minimum radius required for the heaters is 2.

In this way, we use the binary search algorithm to efficiently find the minimum radius for the heaters to cover all houses.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
5        # First, sort the houses and heaters to enable efficient scanning
6        houses.sort()
7        heaters.sort()
8
9        # The function 'can_cover' checks if a given radius 'radius'
10        # is enough to cover all houses by heaters. Returns True if it is, False otherwise.
11        def can_cover(radius):
12            # Get the number of houses and heaters
13            num_houses, num_heaters = len(houses), len(heaters)
14            house_idx, heater_idx = 0, 0   # Start scanning from the first house and heater
15
16            # Iterate over all houses to check coverage
17            while house_idx < num_houses:
18                # If no more heaters are available to check, return False
19                if heater_idx >= num_heaters:
20                    return False
21
22                # Calculate the minimum and maximum coverage range of the current heater
23                min_range = heaters[heater_idx] - radius
24                max_range = heaters[heater_idx] + radius
25
26                # If the current house is not covered, attempt to use the next heater
27                if houses[house_idx] < min_range:
28                    return False
29                # If the current house is outside the current heater's max range,
30                # move to the next heater
31                if houses[house_idx] > max_range:
32                    heater_idx += 1
33                else: # Otherwise the house is covered, move to the next house
34                    house_idx += 1
35
36            return True  # All houses are covered
37
38        # Start with a radius range of 0 to a large number (1e9 is given as a maximum)
39        left, right = 0, int(1e9)
40      
41        # Perform a binary search to find the minimum radius
42        while left < right:
43            mid = (left + right) // 2  # Choose the middle value as the potential radius
44            # If all houses can be covered with the 'mid' radius, search the lower half
45            if can_cover(mid):
46                right = mid
47            else: # If not, search the upper half
48                left = mid + 1
49      
50        # The minimum radius required to cover all houses is 'left' after the loop
51        return left
52
1class Solution {
2    public int findRadius(int[] houses, int[] heaters) {
3        // Sort the array of heaters to perform efficient searches later on
4        Arrays.sort(heaters);
5      
6        // Initialize the minimum radius required for heaters to cover all houses
7        int minRadius = 0;
8
9        // Iterate through each house to find the minimum radius needed
10        for (int house : houses) {
11            // Perform a binary search to find the insertion point or the actual position of the house
12            int index = Arrays.binarySearch(heaters, house);
13
14            // If the house is not a heater, calculate the potential insert position
15            if (index < 0) {
16                index = ~index;  // index = -(index + 1)
17            }
18          
19            // Calculate distance to the previous heater, if any, else set to max value
20            int distanceToPreviousHeater = index > 0 ? house - heaters[index - 1] : Integer.MAX_VALUE;
21
22            // Calculate distance to the next heater, if any, else set to max value
23            int distanceToNextHeater = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;
24          
25            // Calculate the minimum distance to the closest heater for this house
26            int minDistanceToHeater = Math.min(distanceToPreviousHeater, distanceToNextHeater);
27          
28            // Update the minimum radius to be the maximum of previous radii or the minimum distance for this house
29            minRadius = Math.max(minRadius, minDistanceToHeater);
30        }
31
32        // Return the minimum radius required
33        return minRadius;
34    }
35}
36
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find the minimum radius of heaters required to cover all houses.
7    int findRadius(std::vector<int>& houses, std::vector<int>& heaters) {
8        // Sort the house and heater positions to perform binary search later.
9        std::sort(houses.begin(), houses.end());
10        std::sort(heaters.begin(), heaters.end());
11      
12        // Setting initial binary search range.
13        int left = 0, right = 1e9;
14      
15        // Binary search to find the minimum radius.
16        while (left < right) {
17            int mid = (left + right) / 2;
18            // Check if with this radius all houses can be covered.
19            if (canCoverAllHouses(houses, heaters, mid))
20                right = mid;  // Radius can be smaller or is optimal, reduce the search to left half.
21            else
22                left = mid + 1;  // Radius too small, need to increase, search in right half.
23        }
24        // Once left meets right, we've found the smallest radius needed.
25        return left;
26    }
27
28    // Function to check if all houses can be covered with a given radius 'radius'.
29    bool canCoverAllHouses(const std::vector<int>& houses, const std::vector<int>& heaters, int radius) {
30        int numHouses = houses.size(), numHeaters = heaters.size();
31        int i = 0, j = 0;  // Initialize pointers for houses and heaters
32      
33        // Iterate over houses to check coverage.
34        while (i < numHouses) {
35            if (j >= numHeaters) return false;  // Run out of heaters, can't cover all houses.
36            int minHeaterRange = heaters[j] - radius;
37            int maxHeaterRange = heaters[j] + radius;
38          
39            // Current house is not covered by heater j's range.
40            if (houses[i] < minHeaterRange)
41                return false;  // House i can't be covered by any heater, so return false.
42          
43            // Current house is outside the range of heater j, move to next heater.
44            if (houses[i] > maxHeaterRange)
45                ++j;
46            else
47                ++i;  // Current house is covered, move to the next house.
48        }
49        // All houses are covered.
50        return true;
51    }
52};
53
1function findRadius(houses: number[], heaters: number[]): number {
2    // Sort arrays to enable binary search later.
3    houses.sort((a, b) => a - b);
4    heaters.sort((a, b) => a - b);
5
6    // Initialize variables for the lengths of the houses and heaters arrays
7    const totalHouses = houses.length;
8    const totalHeaters = heaters.length;
9
10    // Initialize answer variable to store the final result, the minimum radius needed
11    let minRadius = 0;
12
13    // Initialize houseIndex and heaterIndex for traversing through the houses and heaters.
14    for (let houseIndex = 0, heaterIndex = 0; houseIndex < totalHouses; houseIndex++) {
15        // Calculate current radius for this house to the current heater
16        let currentRadius = Math.abs(houses[houseIndex] - heaters[heaterIndex]);
17
18        // Continue moving to the next heater to find the closest heater for this house
19        while (heaterIndex + 1 < totalHeaters &&
20            Math.abs(houses[houseIndex] - heaters[heaterIndex]) >= Math.abs(houses[houseIndex] - heaters[heaterIndex + 1])) {
21          
22            // Keep track of the minimum radius required for the current house
23            currentRadius = Math.min(Math.abs(houses[houseIndex] - heaters[++heaterIndex]), currentRadius);
24        }
25
26        // Update the minimum radius required for all houses
27        minRadius = Math.max(currentRadius, minRadius);
28    }
29
30    // Return the minimum radius required for all houses
31    return minRadius;
32}
33
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following uses divide and conquer strategy?

Time and Space Complexity

Time Complexity

The time complexity of the solution is determined by the following factors:

  • Sorting the houses and heaters arrays, which takes O(mlogm + nlogn) time, where m is the number of houses and n is the number of heaters.
  • The binary search to find the minimum radius, which takes O(log(max(houses) - min(houses))) iterations. Each iteration performs a check which has a linear pass over the houses and heaters arrays, taking O(m + n) time in the worst case.
  • Combining these, the overall time complexity is O(mlogm + nlogn + (m + n)log(max(houses) - min(houses))).

Space Complexity

The space complexity of the solution is determined by the following factors:

  • The space used to sort the houses and heaters arrays, which is O(m + n) if we consider the space used by the sorting algorithm.
  • The space for the variables and pointers used within the findRadius method and the check function, which is O(1) since it's a constant amount of space that doesn't depend on the input size.

Combining the sorting space and the constant space, the overall space complexity is O(m + n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ