Problem Description

You need to warm all houses using heaters with a fixed radius. Each heater can warm any house that falls within its warming radius on both sides.

You're given two arrays:

• houses: positions of houses on a horizontal line
• heaters: positions of heaters on a horizontal line

Your task is to find the minimum radius that all heaters must have to ensure every house is covered by at least one heater. All heaters will use the same radius value.

A house at position x is warmed by a heater at position y with radius r if the distance between them is at most r, meaning |x - y| <= r.

For example:

• If a heater is at position 5 with radius 2, it can warm houses at positions 3, 4, 5, 6, and 7
• If houses are at [1, 2, 3] and heaters are at [2], a radius of 1 would warm all houses since the heater at position 2 can reach houses at positions 1, 2, and 3

The solution uses binary search on the radius value combined with a greedy checking mechanism. After sorting both arrays, it searches for the smallest radius between 0 and 10^9. For each candidate radius mid, it checks if all houses can be covered by using a two-pointer technique: advancing through houses and heaters to verify if each house falls within the range [heater_position - radius, heater_position + radius] of some heater.

Intuition

The key insight is recognizing this as an optimization problem where we need to find the minimum value (radius) that satisfies a condition (all houses are covered). This pattern naturally suggests binary search on the answer.

Why binary search works here? Consider that if a radius r can warm all houses, then any radius larger than r will also work. Conversely, if radius r cannot warm all houses, then any smaller radius will also fail. This creates a monotonic property: there exists a threshold radius where all values below it fail and all values at or above it succeed.

The challenge then becomes: given a specific radius, how do we efficiently check if all houses can be warmed? After sorting both arrays, we can use a greedy two-pointer approach. We process houses from left to right and for each house, we find if it can be covered by the current heater. If a house is too far to the left of the current heater (outside its range), we know this radius is insufficient. If a house is too far to the right, we move to the next heater and try again.

The sorting is crucial because it allows us to process houses and heaters in order, ensuring we don't miss any coverage gaps. Once sorted, we can confidently say that if we can't cover a house with the current or any subsequent heater, then the radius is too small.

The range for binary search [0, 10^9] is chosen to cover all possible distances since house and heater positions are typically bounded by this range in the problem constraints. We keep narrowing down this range until we find the exact minimum radius needed.

Solution Approach

The implementation consists of two main components: a binary search framework and a verification function.

Step 1: Sorting

houses.sort()
heaters.sort()

Both arrays are sorted to enable efficient checking using a two-pointer technique.

Step 2: Binary Search Setup

left, right = 0, int(1e9)

We initialize the search range where left = 0 (minimum possible radius) and right = 10^9 (maximum possible radius that covers any reasonable distance).

Step 3: Verification Function check(r) This function determines if radius r can warm all houses:

def check(r):
    m, n = len(houses), len(heaters)
    i = j = 0  # pointers for houses and heaters

The checking logic uses two pointers:

• i tracks the current house to be checked
• j tracks the current heater being considered

For each heater at position heaters[j], its coverage range is [heaters[j] - r, heaters[j] + r].

The verification process:

1. If we've run out of heaters (j >= n) but still have houses to cover, return False
2. Calculate the current heater's range: mi = heaters[j] - r and mx = heaters[j] + r
3. If the current house is left of the heater's range (houses[i] < mi), this radius is too small, return False
4. If the current house is right of the heater's range (houses[i] > mx), move to the next heater (j += 1)
5. Otherwise, the house is covered, move to the next house (i += 1)

Step 4: Binary Search Execution

while left < right:
    mid = (left + right) >> 1  # equivalent to (left + right) // 2
    if check(mid):
        right = mid  # radius works, try smaller
    else:
        left = mid + 1  # radius too small, need larger

The binary search narrows down the range:

• If check(mid) returns True, we can potentially use a smaller radius, so we set right = mid
• If check(mid) returns False, we need a larger radius, so we set left = mid + 1

The loop continues until left == right, which gives us the minimum radius needed to cover all houses.

Time Complexity: O((m + n) log(m + n) + (m + n) log(10^9)) where m is the number of houses and n is the number of heaters. The sorting takes O((m + n) log(m + n)) and the binary search performs O(log(10^9)) iterations, each taking O(m + n) time for verification.

Space Complexity: O(1) if we don't count the sorting space, otherwise O(log(m + n)) for the sorting algorithm's recursion stack.

Example Walkthrough

Let's walk through a concrete example with houses = [1, 5, 15] and heaters = [6, 10].

Step 1: Sort both arrays

• Houses: [1, 5, 15] (already sorted)
• Heaters: [6, 10] (already sorted)

Step 2: Binary Search for Minimum Radius

We'll search between left = 0 and right = 1000000000.

Iteration 1:

• mid = (0 + 1000000000) / 2 = 500000000
• Check if radius 500000000 works:
  • Heater at position 6 covers range [-499999994, 500000006]
  • All houses (1, 5, 15) fall within this range
  • Result: TRUE
• Since it works, try smaller: right = 500000000

Iteration 2:

• mid = (0 + 500000000) / 2 = 250000000
• Check if radius 250000000 works:
  • Heater at position 6 covers range [-249999994, 250000006]
  • All houses fall within this range
  • Result: TRUE
• Try smaller: right = 250000000

[Many iterations skipped for brevity]

Key Iteration (when mid = 5):

• mid = 5
• Check if radius 5 works:
  • Start with house at position 1, heater at position 6
  • Heater 6 covers range [1, 11]
  • House 1 is covered (1 ≥ 1 and 1 ≤ 11) ✓
  • House 5 is covered (5 ≥ 1 and 5 ≤ 11) ✓
  • House 15 is NOT covered (15 > 11)
  • Move to next heater at position 10
  • Heater 10 covers range [5, 15]
  • House 15 is covered (15 ≥ 5 and 15 ≤ 15) ✓
  • Result: TRUE
• Try smaller: right = 5

Key Iteration (when mid = 4):

• mid = 4
• Check if radius 4 works:
  • Start with house at position 1, heater at position 6
  • Heater 6 covers range [2, 10]
  • House 1 is NOT covered (1 < 2)
  • Result: FALSE
• Need larger radius: left = 5

Final Result: When left = right = 5, we've found our answer. The minimum radius needed is 5.

Verification of the answer:

• Heater at position 6 with radius 5 warms houses at positions 1 and 5 (range [1, 11])
• Heater at position 10 with radius 5 warms house at position 15 (range [5, 15])
• All houses are covered with radius 5

Solution Implementation

Time and Space Complexity

Time Complexity: O((m + n) * log(m + n) + (m + n) * log(max_distance))

• Sorting houses takes O(m * log(m)) where m is the number of houses
• Sorting heaters takes O(n * log(n)) where n is the number of heaters
• Binary search runs for O(log(max_distance)) iterations, where max_distance is the search space from 0 to 10^9
• Each binary search iteration calls the check() function, which takes O(m + n) time in the worst case as it iterates through all houses and potentially all heaters
• Overall: O(m * log(m) + n * log(n) + (m + n) * log(10^9))
• Since log(10^9) ≈ 30 is a constant, and typically m + n dominates the sorting complexity, this simplifies to O((m + n) * log(m + n) + (m + n) * log(max_distance))

Space Complexity: O(1)

• The sorting operations are done in-place (Python's sort uses Timsort which requires O(min(m, n)) auxiliary space in worst case, but typically O(1) for already sorted or small arrays)
• The algorithm only uses a constant amount of extra variables (i, j, left, right, mid, mi, mx, r)
• No additional data structures are created
• Therefore, the space complexity is O(1) excluding the space used by sorting

Common Pitfalls

1. Incorrect Coverage Check Logic

A common mistake is incorrectly implementing the coverage verification logic, particularly when determining whether to move to the next heater or declare failure.

Pitfall Example:

# WRONG: This logic fails to properly handle all cases
def can_cover_all_houses(radius):
    house_idx = 0
    for heater in heaters:
        while house_idx < len(houses) and houses[house_idx] <= heater + radius:
            house_idx += 1
    return house_idx == len(houses)

This fails because it doesn't check if houses before the heater's minimum coverage are actually covered.

Solution: Ensure you check both boundaries of the heater's coverage range:

if houses[house_idx] < heater_min_coverage:
    return False  # House is too far left
if houses[house_idx] > heater_max_coverage:
    heater_idx += 1  # Try next heater
else:
    house_idx += 1  # House is covered

2. Forgetting to Sort Arrays

The two-pointer technique relies on sorted arrays. Without sorting, the algorithm won't work correctly.

Pitfall Example:

# WRONG: Directly using unsorted arrays
def findRadius(self, houses, heaters):
    # Missing: houses.sort() and heaters.sort()
    left, right = 0, int(1e9)
    # ... rest of the code

Solution: Always sort both arrays before applying the binary search:

houses.sort()
heaters.sort()

3. Off-by-One Error in Binary Search

Using the wrong binary search template can lead to infinite loops or incorrect results.

Pitfall Example:

# WRONG: This can cause infinite loop
while left <= right:  # Should be left < right
    mid = (left + right) // 2
    if check(mid):
        right = mid - 1  # Should be right = mid
    else:
        left = mid + 1

Solution: Use the correct binary search template for finding minimum value:

while left < right:
    mid = (left + right) >> 1
    if check(mid):
        right = mid  # Keep mid as potential answer
    else:
        left = mid + 1

4. Integer Overflow in Binary Search

While less common in Python, calculating mid as (left + right) // 2 can theoretically cause issues with very large numbers.

Pitfall Example:

# Potentially problematic for extremely large values
mid = (left + right) // 2

Solution: Use bit shifting or a safer calculation:

mid = (left + right) >> 1
# OR
mid = left + (right - left) // 2

5. Inefficient Initial Search Range

Setting an unnecessarily large upper bound for the binary search can slow down the algorithm.

Pitfall Example:

# WRONG: Using arbitrary large number
right = int(1e15)  # Too large, wastes iterations

Solution: Use a reasonable upper bound or calculate based on the actual data:

# Option 1: Use reasonable maximum
right = int(1e9)

# Option 2: Calculate based on actual positions
right = max(max(houses) - min(heaters), max(heaters) - min(houses))

6. Not Handling Edge Cases

Failing to consider edge cases like empty arrays or single elements.

Pitfall Example:

# WRONG: No edge case handling
def findRadius(self, houses, heaters):
    houses.sort()
    heaters.sort()
    # Directly proceed without checking if arrays are empty

Solution: Add edge case checks:

if not houses:
    return 0
if not heaters:
    return float('inf')  # Or handle appropriately