Heaters

Medium Binary Search Bisect Original on LeetCode

Heaters is a medium binary search problem solved with the bisect pattern. The best approach, optimal (sort heaters + binary search), runs in O((n + m) log m) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every heater for every house) up.

Problem

Houses and heaters stand on a straight line. You are given their positions in two integer arrays, houses and heaters. All heaters share the same warming radius r: a heater at position t warms every house at a position within distance r of t.

Return the smallest radius r such that every house is warmed by at least one heater.

Examples

Example 1

Input
houses = [2, 5, 9, 14], heaters = [4, 12]
Output
3
Why
House 9 is 3 away from heater 12 (and 5 away from heater 4); every other house is at most 2 from its nearest heater.

Example 2

Input
houses = [1, 6], heaters = [6]
Output
5
Why
House 1 is 5 away from the only heater.

Example 3

Input
houses = [7, 3, 10], heaters = [10, 3, 7]
Output
0
Why
Every house has a heater at its own position, so radius 0 is enough.

Constraints

  • 1 <= houses.length, heaters.length <= 3 · 10^4
  • 1 <= houses[i], heaters[i] <= 10^9
  • Neither array is necessarily sorted.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (check every heater for every house)O(n · m)O(1)
Optimal (sort heaters + binary search)O((n + m) log m)O(1)

1Brute force (check every heater for every house)

TimeO(n · m)Every house is compared with every heater.
SpaceO(1)Two running values.

For each house, compute the distance to every heater and keep the smallest. The answer is the largest of these per-house minimums.

  1. answer = 0.
  2. For each house h: nearest = min over heaters t of |h - t|.
  3. answer = max(answer, nearest).
class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        int answer = 0;
        for (int h : houses) {
            int nearest = Integer.MAX_VALUE;
            for (int t : heaters) nearest = Math.min(nearest, Math.abs(h - t));
            answer = Math.max(answer, nearest);
        }
        return answer;
    }
}

Edge cases to test

  • A single heater far from all houses
  • Houses to the left of every heater or to the right of every heater
  • Heaters at exactly the same positions as houses (answer 0)
  • Unsorted input and repeated positions

Hints

Hint 1

The radius must reach every house, so the answer is the largest 'distance from a house to its nearest heater'.

Hint 2

If the heaters are sorted, the nearest heater to a house is either the first heater at or after it, or the one just before that.

Hint 3

Binary search finds that position in O(log m) per house.

FAQ

What is the best time complexity for Heaters?

Optimal (sort heaters + binary search) runs in O((n + m) log m) time and O(1) extra space. Sorting the heaters costs O(m log m), then each house does one O(log m) search.

Which pattern does Heaters use?

It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.

Is there a brute force solution for Heaters?

Yes. Brute force (check every heater for every house) takes O(n · m) time and O(1) space. For each house, compute the distance to every heater and keep the smallest.

Which edge cases should I test for Heaters?

A single heater far from all houses; Houses to the left of every heater or to the right of every heater; Heaters at exactly the same positions as houses (answer 0); Unsorted input and repeated positions.