Problem Description

The Heaters problem on LeetCode can be paraphrased as follows:

You are given two integer arrays: houses and heaters. Both represent positions on a 1D line. Every house at position houses[i] needs to be warmed by at least one heater. Each heater at position heaters[j] can warm any house within a certain radius r (i.e., any house within [heaters[j] - r, heaters[j] + r]).

The goal is to find the minimum radius r such that every house is within the warming range of at least one heater.

• You can assume there is at least one house and one heater.
• All positions are non-negative integers.
• Heaters and houses can be at the same positions.
• You may not move the houses or heaters.
• Return the minimal possible radius r as an integer.

Thought Process

At first glance, you might think about checking every house against every heater and calculating the distance, then finding the maximum of these minimum distances. This brute-force approach would involve nested loops, which can be inefficient for large inputs.

However, we can optimize by realizing that for each house, we only need to find the closest heater. If we know the minimal distance from each house to any heater, the largest of these distances is the minimal radius required.

Sorting both arrays can help us efficiently find the nearest heater for each house, potentially using binary search or a two-pointer technique, rather than checking every possible pair.

Solution Approach

• Step 1: Sort both arrays.
  Sorting houses and heaters ensures we can process them efficiently and find nearest neighbors easily.
• Step 2: For each house, find the nearest heater.
  For each house, we want to know the distance to its closest heater. We can do this efficiently with binary search (for each house, find the insertion point in heaters), or with a two-pointer scan.
• Step 3: Track the maximum of these minimal distances.
  Since all houses must be covered, the answer is the largest minimal distance between any house and its nearest heater.
• Why sort and use binary search?
  Sorting allows us to use binary search, which is O(log N) per query, versus O(N) if unsorted. This is especially important for large input sizes.
• Alternative: Two-pointer approach.
  After sorting, we can sweep through houses and heaters simultaneously, always keeping track of the closest heater to the current house.

Example Walkthrough

Suppose houses = [1, 2, 3] and heaters = [2].

• Sort both arrays (already sorted in this case).
• For house at position 1: Distance to heater at 2 is |1-2| = 1.
• For house at position 2: Distance to heater at 2 is |2-2| = 0.
• For house at position 3: Distance to heater at 2 is |3-2| = 1.
• The minimal radius needed is the maximum of these distances, which is 1.

If there are multiple heaters, for each house, we find the closest heater (either to the left or right), and take the minimal distance. The answer is still the largest such minimal distance across all houses.

Code Implementation

import bisect

class Solution:
    def findRadius(self, houses, heaters):
        houses.sort()
        heaters.sort()
        res = 0
        for h in houses:
            idx = bisect.bisect_left(heaters, h)
            left = heaters[idx - 1] if idx > 0 else float('-inf')
            right = heaters[idx] if idx < len(heaters) else float('inf')
            dist = min(abs(h - left), abs(h - right))
            res = max(res, dist)
        return res
      

#include <vector>
#include <algorithm>
#include <cmath>

class Solution {
public:
    int findRadius(std::vector<int>& houses, std::vector<int>& heaters) {
        std::sort(houses.begin(), houses.end());
        std::sort(heaters.begin(), heaters.end());
        int res = 0;
        for (int h : houses) {
            auto it = std::lower_bound(heaters.begin(), heaters.end(), h);
            int dist1 = (it == heaters.end()) ? INT_MAX : abs(*it - h);
            int dist2 = (it == heaters.begin()) ? INT_MAX : abs(*(it - 1) - h);
            res = std::max(res, std::min(dist1, dist2));
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int res = 0;
        for (int h : houses) {
            int idx = Arrays.binarySearch(heaters, h);
            if (idx < 0) idx = -idx - 1;
            int left = idx - 1 >= 0 ? heaters[idx - 1] : Integer.MIN_VALUE;
            int right = idx < heaters.length ? heaters[idx] : Integer.MAX_VALUE;
            int dist = Math.min(Math.abs(h - left), Math.abs(h - right));
            res = Math.max(res, dist);
        }
        return res;
    }
}
      

var findRadius = function(houses, heaters) {
    houses.sort((a, b) => a - b);
    heaters.sort((a, b) => a - b);
    let res = 0;
    for (let h of houses) {
        let left = 0, right = heaters.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (heaters[mid] < h) left = mid + 1;
            else right = mid;
        }
        let dist1 = left < heaters.length ? Math.abs(heaters[left] - h) : Infinity;
        let dist2 = left - 1 >= 0 ? Math.abs(heaters[left - 1] - h) : Infinity;
        res = Math.max(res, Math.min(dist1, dist2));
    }
    return res;
};
      

Time and Space Complexity

• Brute-force approach: For each house, check all heaters. Time complexity is O(M*N), where M is the number of houses and N is the number of heaters. Space complexity is O(1) extra.
• Optimized approach (sorting + binary search): Sorting both arrays takes O(M log M + N log N). For each house, binary search in heaters is O(log N), so total is O(M log N). Space is O(1) extra (ignoring input sorting).
• The optimized approach is much faster for large inputs because it avoids unnecessary comparisons.

Summary

The key insight for the Heaters problem is that each house only cares about its nearest heater. By sorting both arrays and using binary search or two pointers, we efficiently find the minimum radius needed to warm every house. The algorithm is elegant because it leverages sorting and searching, reducing a potentially quadratic problem to a much faster solution.