17 lines of code O(N logN) simple Java Solution


  • 2
    M

    Just traverse houses array from left to right and greedily pickup the closest heater.

    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(houses);
            Arrays.sort(heaters);
            int heaterIdx = 0;
            int res = 0;
            for (int i = 0; i < houses.length; i++) {
                while (heaterIdx != heaters.length - 1 && Math.abs(heaters[heaterIdx + 1] - houses[i]) <= Math.abs(heaters[heaterIdx] - houses[i])) {
                    heaterIdx++;
                }
                
                res = Math.max(res, Math.abs(heaters[heaterIdx] - houses[i]));
            }
            
            return res;
        }
    }
    

  • 0
    S

    @mihania Time complexity is O(nlogn + mlogm) because you don't know which array is shorter.


Log in to reply
 

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