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