Solution Approach

The solution uses binary search on the answer space combined with a greedy validation function.

Step 1: Sorting Both arrays are sorted to enable efficient checking using a two-pointer technique.

Step 2: Binary Search Setup

• left = 0 (minimum possible radius)
• right = 10^9 (maximum possible radius)
• first_true_index = -1 (tracks the answer)

Step 3: Feasible Function The feasible(radius) function determines if all houses can be covered with the given radius. This creates a boolean pattern:

radius:   0    1    2    3    4    5    ...
feasible: false false false false false true ...

The checking logic uses two pointers:

• For each heater, its coverage range is [heater - radius, heater + radius]
• If a house is left of all heater ranges, the radius is too small
• If a house is beyond current heater's range, try the next heater

Step 4: Binary Search Template

left, right = 0, int(1e9)
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1  # Try smaller radius
    else:
        left = mid + 1   # Need larger radius

return first_true_index

Time Complexity: O((m + n) log(m + n) + (m + n) log(10^9)) where m is houses, n is heaters. Space Complexity: O(1) excluding sorting space.

Example Walkthrough

Let's walk through 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 with template

• left = 0, right = 10^9, first_true_index = -1

Key iterations (skipping large radius checks):

When mid = 5:

• Check feasible(5):
  • Heater 6 covers range [1, 11]
  • House 1: 1 ≥ 1 and 1 ≤ 11 → covered ✓
  • House 5: 5 ≥ 1 and 5 ≤ 11 → covered ✓
  • House 15: 15 > 11 → try next heater
  • Heater 10 covers range [5, 15]
  • House 15: 15 ≥ 5 and 15 ≤ 15 → covered ✓
  • Result: True
• first_true_index = 5, right = 4

When mid = 2 (in range [0, 4]):

• Check feasible(2):
  • Heater 6 covers range [4, 8]
  • House 1: 1 < 4 → not covered!
  • Result: False
• left = 3

When mid = 4 (in range [3, 4]):

• Check feasible(4):
  • Heater 6 covers range [2, 10]
  • House 1: 1 < 2 → not covered!
  • Result: False
• left = 5

Loop ends: left = 5 > right = 4

Answer: first_true_index = 5

Verification:

• Heater 6 with radius 5: covers [1, 11] → houses 1 and 5
• Heater 10 with radius 5: covers [5, 15] → house 15
• All houses covered with minimum radius 5.

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. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with right = mid instead of the standard template.

Incorrect:

while left < right:
    mid = (left + right) // 2
    if feasible(mid):
        right = mid
    else:
        left = mid + 1
return left

Correct (template-compliant):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

The template approach explicitly tracks the answer and handles edge cases consistently.

2. Incorrect Coverage Check Logic

Not checking both boundaries of the heater's coverage range.

Incorrect:

def feasible(radius):
    for heater in heaters:
        while house_idx < len(houses) and houses[house_idx] <= heater + radius:
            house_idx += 1
    return house_idx == len(houses)  # Missing left boundary check!

Correct:

if houses[house_idx] < min_coverage:
    return False  # House is too far left of all heaters

3. Forgetting to Sort Arrays

The two-pointer feasibility check requires sorted arrays.

# Always sort both arrays first
houses.sort()
heaters.sort()

4. Not Handling Edge Cases

When all houses are covered by the first heater, or when arrays have different sizes.

The feasible function handles these automatically with proper two-pointer logic.