Simple Java Solution with heater pointer


  • 1
    E

    I basically went through the whole process:

    1. O(mn) easiest one > Timeout
    2. O(mlogn)
    3. The following one:

    If n < m, I think it would have a higher time complexity than 2. But this one does not use binary search, much simpler though:P

    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            int minRadius = 0, h = 0, len = heaters.length;
            Arrays.sort(heaters);
            Arrays.sort(houses);
            for (int house : houses) {
                while (h + 1 < len && heaters[h + 1] < house) h++;
                int minLocal = 0;
                if (heaters[h] < house)
                    minLocal = Math.max(minLocal, house - heaters[h]);
                if (heaters[h] > house)
                    minLocal = Math.max(minLocal, heaters[h] - house);
                if (h + 1 < len)
                    minLocal = Math.min(minLocal, heaters[h + 1] - house);
                minRadius = Math.max(minRadius, minLocal);
            }
            return minRadius;
        }
    }
    

Log in to reply
 

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