Heaters

LeetCode 475 | Difficulty: Medium

Medium

Problem Description

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range.

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Notice that all the heaters follow your radius standard, and the warm radius will be the same.

Example 1:

Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: 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
Explanation: 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

Constraints:

- `1 <= houses.length, heaters.length <= 3 * 10^4`

- `1 <= houses[i], heaters[i] <= 10^9`

Topics: Array, Two Pointers, Binary Search, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 116 ms)

Metric	Value
Runtime	116 ms
Memory	45 MB
Date	2022-02-05

Solution

public class Solution {
    public int FindRadius(int[] houses, int[] heaters) {
    int n = houses.Length;
    int m = heaters.Length;

    Array.Sort(houses);
    Array.Sort(heaters);
    int j=0, max = 0;
    for (int i = 0; i < n; i++)
    {
        while(j+1<m && Math.Abs(houses[i]-heaters[j+1]) <= Math.Abs(heaters[j] - houses[i]))
        {
            j++;
        }
        max = Math.Max(max, Math.Abs(heaters[j]-houses[i]));        
    }
    return max;
    }
}

📜 1 more C# submission(s)

Submission (2022-02-05) — 174 ms, 43.5 MB

public class Solution {
    public int FindRadius(int[] houses, int[] heaters) {
        int n = houses.Length;
    int m = heaters.Length;
    
    Array.Sort(houses);
    Array.Sort(heaters);
    int[] result = new int[houses.Length];
    for (int i = 0; i < result.Length; i++)
    {
        result[i] = Int32.MaxValue;
    }
    for (int i = 0, h =0; i <n && h<m; )
    {
        if(houses[i]<=heaters[h])
        {
            result[i] = heaters[h]-houses[i];
            i++;
        }
        else h++;
    }
    
    for (int i = n-1, h=m-1; i >= 0 && h>=0; )
    {
        if(houses[i] >= heaters[h])
        {
            result[i] = Math.Min(result[i], houses[i]-heaters[h]);
            i--;
        }
        else h--;
    }
    
    return result.Max();
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Precisely define what the left and right boundaries represent, and the loop invariant.