#475

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Heaters

Determine the minimum heater radius to cover all houses using a binary search over potential radius values efficiently.

array two pointers binary search sorting

Problem Statement

Winter is coming, and you are tasked with ensuring all houses along a horizontal street are warmed. Each house can be warmed by a heater if it lies within the heater's warm radius. You are given two arrays representing the positions of houses and heaters.

Your goal is to determine the minimum standard radius for the heaters such that every house is within the warming range of at least one heater. Return this minimum radius as an integer. Constraints ensure large input sizes, emphasizing the need for an efficient binary search strategy.

Examples

Example 1

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

Output: 1

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

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

Example details omitted.

Constraints

1 <= houses.length, heaters.length <= 3 * 104
1 <= houses[i], heaters[i] <= 109

Solution Approach

Sort Houses and Heaters

Begin by sorting both the houses and heaters arrays. Sorting ensures that distance checks can be done efficiently, enabling two-pointer or binary search techniques to quickly find the nearest heater for each house without scanning the entire array.

Binary Search Over Radius

Use binary search on the possible radius values. For a candidate radius, check whether all houses are within range of at least one heater. If a radius works, attempt a smaller radius; if it fails, increase the radius. This pattern leverages the monotonicity of the coverage condition.

Two-Pointer Nearest Heater Check

Implement a two-pointer approach to find the nearest heater for each house efficiently. This ensures that for each candidate radius, the check runs in linear time relative to the number of houses, avoiding unnecessary repeated computations and optimizing performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n + m log m) where n and m are the numbers of houses and heaters. Each binary search check can run in O(n) with a two-pointer nearest heater scan, leading to total time O((n + m) log(maxDistance)). Space is O(1) or O(n + m) if arrays are copied during sorting.

What Interviewers Usually Probe

Sorting both arrays is critical to avoid inefficient distance checks.
Binary search over the radius shows understanding of monotonic answer patterns.
Two-pointer or direct nearest heater evaluation ensures each candidate radius can be validated efficiently.

Common Pitfalls or Variants

Common pitfalls

Assuming the nearest heater is always to the left or right without checking both sides.
Using linear search for each house-heater pair, causing timeouts on large inputs.
Forgetting to sort the heaters or houses, which breaks the binary search assumptions.

Follow-up variants

Determine the minimum number of heaters needed if all have a fixed radius.
Compute the maximum house distance from its nearest heater instead of minimal radius.
Place heaters optimally along the street to minimize total radius sum.

FAQ

What is the best way to find the minimum radius for the Heaters problem?

Sort both houses and heaters, then perform a binary search over possible radius values while checking coverage with a two-pointer nearest heater scan.

Can this problem be solved without binary search?

Yes, a linear sweep with two pointers can check distances, but binary search over radius is more efficient for large inputs.

Why do we sort the heaters and houses first?

Sorting allows efficient nearest-heater checks and ensures that the binary search over radius is valid and monotonic.

What edge cases should I consider in Heaters?

Houses before the first heater, houses after the last heater, and multiple heaters at the same position are common edge cases.

Does GhostInterview handle the binary search over valid answer space pattern?

Yes, it specifically guides the search over numeric radius values, ensuring minimal valid coverage is computed correctly.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        houses.sort()
        heaters.sort()

        def check(r):
            m, n = len(houses), len(heaters)
            i = j = 0
            while i < m:
                if j >= n:
                    return False
                mi = heaters[j] - r
                mx = heaters[j] + r
                if houses[i] < mi:
                    return False
                if houses[i] > mx:
                    j += 1
                else:
                    i += 1
            return True

        left, right = 0, int(1e9)
        while left < right:
            mid = (left + right) >> 1
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

Continue Practicing

#532 k diff pairs in an array #350 intersection of two arrays ii #349 intersection of two arrays