Java TreeSet log(n) Solution with explanation


  • 8

    Initially I was trying TreeSet as it provides easier way to find the lowerBound and upperBound. While I mistakenly reversed the min and max relationship when updating the global min radius result. Thanks to @ckcz123 's solution and I realized my error and made it right.
    The idea using TreeSet is first put heaters' location into the tree, then iterate the houses' location finding the smallest radius with which one of the closest heaters may cover. Say heaters[1, 4] , houses[1,2,3,4]. When we scan the house = 1, found closest heater is at 1, so the global max till house at 1 is 0; then when house = 2, found the closest heater is min(house at 2 - heater at 1, heater at 4 - house at 2) = 1, which means the heater at 1 can cover the house at 2 and we do not need to use heater at 4. In the end, we may found the global res (min radius required) and remember that some of the heaters may not be effectively used as long as all the houses are already covered. O(logn) for TreeSet operations in this solution, but need O(heater) space which is not as good as binary search solution.

    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            TreeSet<Integer> treeset = new TreeSet<>();
            for (int heater : heaters) treeset.add(heater);
            int res = 0;
            for (int house : houses) {
                Integer upper = treeset.ceiling(house); 
                Integer lower = treeset.floor(house);
                res = Math.max(res, Math.min(upper == null ? Integer.MAX_VALUE : upper - house, lower == null ? Integer.MAX_VALUE : house - lower));
            }
            return res;
        }
    }
    

  • 0
    H

    Just curious how come this is O(log n) solution? If you are scanning all the houses shouldn't it be O(n) solution?


  • 0

    @harshaneel said in Java TreeSet log(n) Solution with explanation:

    Just curious how come this is O(log n) solution? If you are scanning all the houses shouldn't it be O(n) solution?

    O(logn) is just for TreeSet operation, not the time complexity of the entire solution.


  • 0
    H

    @sheva Oh yes. You have mentioned that in the last line. Missed that.


Log in to reply
 

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