Another easy-understanding solution based on the binary search.

  • 0

    This problem is really like the problem:
    And the explanation is

    Basic idea, I set the high bound as the highest range a heater could have, that is, the right-most heater or house of the road. And the low bound as 0, which is the case that all the heater are exactly locate on each house.
    Then we do the binary search to figure out if the mid satisfy the need. If it does, then we keep it in the binary search, and set h = m. if not, we need increase the low bound to m + 1.
    Then we will find the lowest range that satisfies our need.

    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            if(heaters.length == 0 || houses.length == 0) return 0;
            int l = 0;
            int h = Math.max(houses[houses.length-1], heaters[heaters.length-1]); 
                int m = (l + h) / 2;
                int j = 0;
                for(int i : heaters){
                    while(j < houses.length && (i - m) <= houses[j] && (i + m) >= houses[j]){
                if(j == houses.length) h = m;
                else l = m + 1;
            return l;

Log in to reply

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