Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 * 1041 <= houses[i], heaters[i] <= 109Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Two Pointers · Binary Search
[1,2,3] [2]
[1,2,3,4] [1,4]
[1,5] [2]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #475: Heaters
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int res = 0;
for (int x : houses) {
int i = Arrays.binarySearch(heaters, x);
if (i < 0) {
i = ~i;
}
int dis1 = i > 0 ? x - heaters[i - 1] : Integer.MAX_VALUE;
int dis2 = i < heaters.length ? heaters[i] - x : Integer.MAX_VALUE;
res = Math.max(res, Math.min(dis1, dis2));
}
return res;
}
}
// Accepted solution for LeetCode #475: Heaters
func findRadius(houses []int, heaters []int) int {
sort.Ints(houses)
sort.Ints(heaters)
m, n := len(houses), len(heaters)
check := func(r int) bool {
var i, j int
for i < m {
if j >= n {
return false
}
mi, mx := heaters[j]-r, heaters[j]+r
if houses[i] < mi {
return false
}
if houses[i] > mx {
j++
} else {
i++
}
}
return true
}
left, right := 0, int(1e9)
for left < right {
mid := (left + right) >> 1
if check(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
# Accepted solution for LeetCode #475: Heaters
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
// Accepted solution for LeetCode #475: Heaters
struct Solution;
impl Solution {
fn distance(a: i32, b: i32) -> i32 {
(a - b).abs()
}
fn find_radius(mut houses: Vec<i32>, mut heaters: Vec<i32>) -> i32 {
houses.sort_unstable();
heaters.sort_unstable();
let mut i = 0;
let mut j = 0;
let n = houses.len();
let m = heaters.len();
let mut max = 0;
while i < n {
while j + 1 < m
&& Self::distance(heaters[j + 1], houses[i])
<= Self::distance(heaters[j], houses[i])
{
j += 1;
}
max = i32::max(Self::distance(houses[i], heaters[j]), max);
i += 1;
}
max
}
}
#[test]
fn test() {
let houses = vec![1, 2, 3];
let heaters = vec![2];
assert_eq!(Solution::find_radius(houses, heaters), 1);
let houses = vec![1, 2, 3, 4];
let heaters = vec![1, 4];
assert_eq!(Solution::find_radius(houses, heaters), 1);
}
// Accepted solution for LeetCode #475: Heaters
function findRadius(houses: number[], heaters: number[]): number {
houses.sort((a, b) => a - b);
heaters.sort((a, b) => a - b);
const m = houses.length,
n = heaters.length;
let ans = 0;
for (let i = 0, j = 0; i < m; i++) {
let cur = Math.abs(houses[i] - heaters[j]);
while (
j + 1 < n &&
Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])
) {
cur = Math.min(Math.abs(houses[i] - heaters[++j]), cur);
}
ans = Math.max(cur, ans);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.
Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.