Heaters

Medium
1374.

Heaters

Heaters is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Microsoft interviews.

Houses and heaters stand at integer positions on a straight road: houses[i] is the position of a house and heaters[j] the position of a heater. Neither array is sorted, and a position may appear more than once.

Every heater is set to the same warming radius r: a heater at p warms every house whose position lies in [p - r, p + r].

Return the smallest non-negative integer radius that warms every house.

Example 1

Input
houses = [1,5], heaters = [2]
Output
3
Explanation
The single heater must reach the house at 5, three steps away.

Example 2

Input
houses = [3,9,14], heaters = [12,4]
Output
3
Explanation
House 3 is 1 from heater 4, house 9 is 3 from heater 12 and house 14 is 2 from heater 12; the worst house needs 3.

Example 3

Input
houses = [7], heaters = [7]
Output
0

Constraints

  • 1 <= houses.length, heaters.length <= 3 * 10^4
  • 1 <= houses[i], heaters[j] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Heaters — Solution in Python, Java & C++

Heaters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Heaters is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Microsoft interviews.

Problem statement

Houses and heaters stand at integer positions on a straight road: houses[i] is the position of a house and heaters[j] the position of a heater. Neither array is sorted, and a position may appear more than once.

Every heater is set to the same warming radius r: a heater at p warms every house whose position lies in [p - r, p + r].

Return the smallest non-negative integer radius that warms every house.

Example 1

Input: houses = [1,5], heaters = [2]
Output: 3
Explanation: The single heater must reach the house at 5, three steps away.

Example 2

Input: houses = [3,9,14], heaters = [12,4]
Output: 3
Explanation: House 3 is 1 from heater 4, house 9 is 3 from heater 12 and house 14 is 2 from heater 12; the worst house needs 3.

Example 3

Input: houses = [7], heaters = [7]
Output: 0

Constraints

  • 1 <= houses.length, heaters.length <= 3 * 10^4
  • 1 <= houses[i], heaters[j] <= 10^9

Hints for Heaters

  1. Hint 1

    The radius has to cover the house that is farthest from its nearest heater, so the answer is a maximum over houses of a minimum over heaters.

  2. Hint 2

    For one house only two heaters matter: the closest one at or to its right and the closest one to its left.

  3. Hint 3

    Sort the heaters and binary-search each house's insertion point; take the smaller of the two neighbouring distances.

How to solve Heaters

The minimum radius equals the largest distance from any house to its nearest heater. With the heaters sorted, a house's nearest heater is one of the two that bracket its position, which binary search finds in logarithmic time.

Approach

  1. Sort a copy of heaters.
  2. For each house at x, find the first heater index i with heaters[i] >= x (lower bound).
  3. The house's distance is the smaller of heaters[i] - x (if i is in range) and x - heaters[i - 1] (if i > 0).
  4. Return the maximum of these distances over all houses.

Why it works

A radius r warms a house exactly when some heater lies within r of it, i.e. when r is at least the house's nearest-heater distance. So r works for all houses precisely when it is at least the largest of those distances, and that largest distance is the minimum. Among heaters on the right of x the first is the closest, and among those on the left the last is the closest, so the two bracketing heaters are the only candidates.

Complexity

  • Time — O((n + m) log m)
  • Space — O(m) for the sorted copy

Pitfalls

  • A house to the left of every heater (or right of every heater) has only one neighbour — guard both indices.
  • Houses do not need sorting for the binary-search version; only the heaters do.
  • The answer is a maximum of minima — taking the minimum over all pairs answers a different question.

Reference solution

Python

from typing import List
import bisect

def findRadius(houses: List[int], heaters: List[int]) -> int:
    hs = sorted(heaters)
    best = 0
    for x in houses:
        i = bisect.bisect_left(hs, x)
        d = 1 << 31
        if i < len(hs):
            d = hs[i] - x
        if i > 0:
            d = min(d, x - hs[i - 1])
        best = max(best, d)
    return best

Java

public static int findRadius(int[] houses, int[] heaters) {
    int[] hs = heaters.clone();
    Arrays.sort(hs);
    int best = 0;
    for (int x : houses) {
        int lo = 0, hi = hs.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (hs[mid] < x) lo = mid + 1; else hi = mid;
        }
        int d = Integer.MAX_VALUE;
        if (lo < hs.length) d = hs[lo] - x;
        if (lo > 0) d = Math.min(d, x - hs[lo - 1]);
        best = Math.max(best, d);
    }
    return best;
}

C++

int findRadius(vector<int>& houses, vector<int>& heaters) {
    vector<int> hs(heaters);
    sort(hs.begin(), hs.end());
    int best = 0;
    for (int x : houses) {
        int i = lower_bound(hs.begin(), hs.end(), x) - hs.begin();
        int d = INT_MAX;
        if (i < (int)hs.size()) d = hs[i] - x;
        if (i > 0) d = min(d, x - hs[i - 1]);
        best = max(best, d);
    }
    return best;
}

JavaScript

var findRadius = function(houses, heaters) {
    var hs = heaters.slice().sort(function(a, b) { return a - b; });
    var best = 0;
    for (var i = 0; i < houses.length; i++) {
        var x = houses[i];
        var lo = 0, hi = hs.length;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (hs[mid] < x) lo = mid + 1; else hi = mid;
        }
        var d = 2147483647;
        if (lo < hs.length) d = hs[lo] - x;
        if (lo > 0 && x - hs[lo - 1] < d) d = x - hs[lo - 1];
        if (d > best) best = d;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms