Simple Java Solution with 2 Pointers


  • 50

    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;
        }
    }
    

  • 5

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


  • 4

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


  • 0
    This post is deleted!

  • 0
    B

    Very nice solutions! Thanks for sharing.


  • 1
    Z

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


  • 15
    J

    @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]


  • 0
    L

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


  • 2

    @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.


  • 0
    L

    @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.


  • 5
    I

    maybe better to write the condition this way:

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

  • 2
    B

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


  • 2
    K

    妙,妙啊~~~~~~~~


  • 0
    L

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


  • 0
    L

    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.


  • 0

    @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]);
    

  • 1
    L

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


  • 1

    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;
        }

  • 0
    Y

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


Log in to reply
 

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