Simple Java Solution with 2 Pointers

• Based on 2 pointers, the idea is to find the nearest heater for each house, by comparing the next heater with the current heater.

``````public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);

int i = 0, j = 0, res = 0;
while (i < houses.length) {
while (j < heaters.length - 1
&& Math.abs(heaters[j + 1] - houses[i]) <= Math.abs(heaters[j] - houses[i])) {
j++;
}
res = Math.max(res, Math.abs(heaters[j] - houses[i]));
i++;
}

return res;
}
}
``````

Updated solution inspired by @StefanPochmann

``````public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);

int i = 0, res = 0;
for (int house : houses) {
while (i < heaters.length - 1 && heaters[i] + heaters[i + 1] <= house * 2) {
i++;
}
res = Math.max(res, Math.abs(heaters[i] - house));
}

return res;
}
}
``````

• Try `for (int house : houses) {`, I think that's much nicer.

• @StefanPochmann Yup, and I think your conversion to `while heaters[i] + heaters[i+1] <= 2 * x:` is much better :)

• This post is deleted!

• Very nice solutions! Thanks for sharing.

• Can you explain why use as a condition `heaters[i] + heaters[i + 1] <= house * 2` in the updated solution?
Thank you!

• @zeqli
heaters[i] + heaters[i + 1] <= house * 2
is checking if house is closer to heaters[i] or heaters[i + 1]

The following same function is checking if house is less than half of the two heaters
If it is less than half, it is closer to the heaters[i] and vice versa
(heaters[i] + heaters[i + 1]) / 2 <= house

For example,
heaters[i] is at 2 while heaters[i+1] is at 6. half of 2 and 6 is 4. If house is less than 4 then it is closer to heaters[i] but if it is larger than 4, then it is closer to heaters[i+1]

• Is the time complexity of this O(mn) where m is the length of houses, n is the length of heaters?

• @lekzeey No, sorting of houses O(nlogn) and heaters O(mlogm), and the main part of this algorithm with two pointer is O(n + m), you can think of each element in houses and heaters are visited once.

• @lekzeey If you not pre-sort the arrays and for every house, you iterate the heaters, the time complexity is O(mn).But this will cause time out for some large case.

• maybe better to write the condition this way:

``````heaters[index+1] - house < house - heaters[index]
``````

• heaters[i] + heaters[i + 1] <= house * 2 is not good because it is not easy to understand.

• 妙，妙啊~~~~~~~~

• @tankztc could u explain why it is O(m + n) for two pointer part? Thanks!

• Could you please explain why <=? I wrote < at first and thought it didn't matter much but i got wrong answer and I couldn't figure out the difference.

• @ljzhanglc Print the cases that you affected (i.e., the `==` cases) and you'll likely understand:

``````            if (j < heaters.length - 1
&& Math.abs(heaters[j + 1] - houses[i]) == Math.abs(heaters[j] - houses[i]))
System.out.println(houses[i] + " " + heaters[j] + " " + heaters[j + 1]);
``````

• @StefanPochmann
Thanks a lot! I didn't think heaters can be on the same spot, that's the problem.

• The difficulty of this problem is to understand `Math.abs(heaters[i] - house) >= Math.abs(heaters[i + 1] - house`
Let's us understand this with a example:
`houses: 1, 2, 3, 4`
`heaters: 1, 4`
For house `1`, heater `1` is closer to it than heater `4`, so we don't move `i` to `i + 1`.
For house `2`, it is same. heater `1` is closer.
For house `3`, it is clear that heater `1` no longer closer, so we move `i` to `i + 1`.
For house 4, continue....

The idea here is we move the heater to rightward in case it is closer to the given house.

``````    public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);

int i = 0, res = 0;
for(int house: houses){
while(i + 1 < heaters.length && Math.abs(heaters[i] - house) >= Math.abs(heaters[i + 1] - house)){
i++;
}
res = Math.max(res, Math.abs(heaters[i] - house));
}
return res;
}``````

• @zeqli |A-X| <= |B-X| && A >=B
We can have B-X<=A-X<=X-B
==>A+B<=2X

• ``````class Solution {
public int findRadius(int[] houses, int[] heaters) {

Arrays.sort(houses);
Arrays.sort(heaters);

int res = 0, r = 0, j = 0;
for(int i=0; i < houses.length; i++){
r = 0;
while(j < heaters.length
&& houses[i] > heaters[j])
++j;
if(j < heaters.length){
r = heaters[j]-houses[i];
if(j-1 >= 0)
r = Math.min(r, houses[i]-heaters[j-1]);
}else
r = Math.abs(heaters[j-1]-houses[i]);
res = Math.max(res, r);
}

return res;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.