Binary Search & Two pointer (Java)


  • 0

    The first solution I came up with is for each house, find the two heaters between which the house is located using binary search. We can using Arrays.binarySearch() Function. The time complexity for this process is O(houses*lg(heaters))

    Then I realized that since houses and heaters are all sorted. We can search for the position where the houses located by using two pointers instead of using binary search.

    i: house index   j: heater index
    max: minimum radius of heater
    
    IF houses[i]<heaters[j]: house i is located between heater j-1( If it exist) and heater j. update max
    IF houses[i]==heaters[j]: continue
    IF houses[i]>heaters[j]: increase j, we have not find the location
    

    The time complexity for this process is O(houses+heaters)

    I find it's quite annoying to handle the edge cases in a elegant way.

    Solution 1:

    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(houses);
            Arrays.sort(heaters);
            int max=0;
            for(int i=0;i<houses.length;i++){
                int index=Arrays.binarySearch(heaters,houses[i]);
                if(index<0){
                    index=-(index+1);
                    if(index==0) max=Math.max(max,heaters[0]-houses[i]);
                    else if(index==heaters.length) max=Math.max(max,houses[i]-heaters[heaters.length-1]);
                        else max=Math.max(max,Math.min(houses[i]-heaters[index-1], heaters[index]-houses[i]));
                }
            }
            return max;
        }
    }
    

    Solution 2:

    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(houses);
            Arrays.sort(heaters);
            int max=0;
            int i=0, j=0;
            while(i<houses.length){
                if(j==heaters.length) {
                    max=Math.max(max,houses[i]-heaters[j-1]);
                    i++;
                    continue;
                }
                if(houses[i]<=heaters[j]){
                    max=Math.max(max,Math.min(j-1>=0?houses[i]-heaters[j-1]:Integer.MAX_VALUE, heaters[j]-houses[i]));
                    i++;
                }else j++;
            }
            return max;
        }
    }
    

Log in to reply
 

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