NearestRetailer

https://leetcode.com/discuss/interview-question/1692516/Amazon-OA1-full-time-question-Jan-2022

Solution:

https://leetcode.com/discuss/interview-question/1692516/Amazon-OA1-full-time-question-Jan-2022

Using a Treemap and taking advantage of the fact that y is between 1 and 100. I bucket sort it in a treemap, treemap functions are log(n) but turn into log(100). Possibly missed edge cases but the happy path seems to work and the logic makes sense. O(nlogn) I think, comments are in the code, the formatting is messed up but not sure how to change it. There may be an easier way too, but I think the key is abusing the fact that the y values are so low, since there's no other reason they would have made the condition 1<=request[i][1]<=100.

// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
int [][] retailers = new int[][]{{1,2},{2,3},{1,5}};
int [][] requests = new int[][]{{1,1},{1,4}};
System.out.println(Arrays.toString(countNumberOfRetailers(retailers,requests)));
}
public static int [] countNumberOfRetailers(int [][] retailers, int[][] requests){
//bucket sort since we know y is between 1 and 100
TreeMap<Integer, List<int[]>> map = new TreeMap<>();
Arrays.sort(retailers, (a,b)->{
return b[1]-a[1];
});
ArrayList<int[]> current = new ArrayList<>();
//keep a running total of valid retailers at each existing Y
//clone can only be called at most 100 times so amortized 100*N+O(nlogn) since there can be only at most 100 keys (different y coordinates)
for(int[] retailer: retailers){
int y = retailer[1];
List<int[]> temp = map.get(y);
if(!map.containsKey(y)){
temp = (ArrayList)current.clone();
}
temp.add(retailer);
current.add(retailer);
map.put(y, temp);
}

    //at most 100*nlogn
    for(Map.Entry<Integer,List<int[]>> entry: map.entrySet()){
        List<int[]> list = entry.getValue();
        //sort by x
        Collections.sort(list, (a,b)->{
            return a[0] - b[0]; 
        });
        map.put(entry.getKey(),list);
    }
    
    //now for each request we can grab a list of valid retailers eliminating y and binary search the sorted list O(logn)
    int [] res = new int[requests.length];
    for(int i=0; i<requests.length;++i){
        int [] request = requests[i];
        List<int[]> sortedList = map.ceilingEntry(request[1]).getValue();
        //System.out.println(sortedList.size()+" "+Arrays.toString(request));
        //binary search
        int start = 0;
        int end = sortedList.size()-1;
        int x = request[0];
        while(start<end){
            int mid = start+(end-start)/2;
            if( x < sortedList.get(mid)[0]){
                start=mid+1;
            }else{
                end = mid;
            }
        }
        res[i] = sortedList.size()-start;
    }
    return res;
    
}
}