Check how many rectangles cover a point
I have a list of points [[1,2], [2,3], [1,5]] each point represents a rectangle with dimensions [0,0], [x, 0], [0, y], [x,y].
Here for example for [1,2], x =1 and y = 2 so rectangle dimentions are [0,0], [1, 0], [0, 2], [1,y]
Now I have another list of points [[1,1], [1,4]]. Now my task is to check how many rectangles can cover these points.
For example: [[1,1], [1,4]
[1,1] is covered by [1,2], [2,3], [1,5] so 3.
[1,4] is covered by [1,5] only so 1.
Here is my program:
public List<Integer> process(List<List<Integer>> inp1, List<List<Integer>> inp2) {
List<Integer> list = new ArrayList<>();
for (List<Integer> p1 : inp2) {
int a = p1.get(0), b = p1.get(1);
int count = 0;
for (List<Integer> p2 : inp1) {
int c = p2.get(0), d = p2.get(1);
if (c >= a && d >= b)
count++;
}
list.add(count);
}
return list;
}
This program works for small inputs as time complexity is O(N^2), but my input list can be very large so the program fails with time-out errors. How to improve this code? I am looking for a condition to break the inner loop or some other better approach to solve this task.
Constraints:
Size of the input list is 1 to 10^5.
x coordinate of inp1 is 1 to 10^9
y coordinate of inp1 is 1 to 100
x coordinate of inp2 is 0 to 10^9
y coordinate of inp2 is 0 to 100
Update:
I have tried the approach mentioned by @user1984, but still, the code fails when the input range is very high with time-out errors. How can I improve this solution further?
public static void main(String[] args) {
System.out.println(process(Arrays.asList(Arrays.asList(1, 2), Arrays.asList(2, 3), Arrays.asList(1, 5)),
Arrays.asList(Arrays.asList(1, 1), Arrays.asList(1, 4))));
}
public static List<Integer> process(List<List<Integer>> inp1, List<List<Integer>> inp2) {
Map<Integer, List<Integer>> map = new TreeMap<>();
for (List<Integer> list : inp1) {
int k = list.get(0);
List<Integer> v = map.getOrDefault(k, new ArrayList<>());
map.put(k, v);
v.add(list.get(1));
}
List<Integer> keys = new ArrayList<>(map.keySet());
for (int key : keys) {
List<Integer> list = map.get(key);
Collections.sort(list);
}
List<Integer> result = new ArrayList<>();
for (List<Integer> list : inp2) {
int x = list.get(0);
int y = list.get(1);
// Get the starting index for x coordinate
int k = startsFrom(keys, x);
if (k == -1) {
result.add(0);
} else {
int count = 0;
for (int i = k; i < keys.size(); i++) {
List<Integer> values = map.get(keys.get(i));
// Get the starting index for y coordinate
int k1 = startsFrom(values, y);
if (k1 != -1) {
count += values.size() - k1;
}
}
result.add(count);
}
}
return result;
}
// Get the index where target can be found in list
private static int startsFrom(List<Integer> list, int target) {
int s = 0, e = list.size() - 1;
int k = -1;
while (s <= e) {
int m = (s + e) / 2;
if (list.get(m) < target) {
s = m + 1;
} else {
k = m;
e = m - 1;
}
}
return k;
}
update: Additional Test case:
public static void main(String[] args) {
System.out.println(process(Arrays.asList(a(6, 15), a(6, 12), a(9, 13), a(9, 16), a(10, 15), a(14, 15),
a(13, 14), a(15, 20), a(11, 16), a(10, 18), a(13, 12), a(10, 20),
a(6, 16), a(5, 11), a(7, 10), a(13, 11), a(9, 12), a(14, 17),
a(9, 17), a(8, 16), a(11, 19), a(9, 11), a(10, 12), a(13, 17),
a(8, 14), a(14, 12), a(12, 14), a(15, 12), a(5, 15), a(7, 18),
a(13, 15), a(5, 16), a(7, 16), a(7, 11), a(14, 18), a(6, 18),
a(12, 12), a(5, 14), a(8, 12), a(6, 17), a(6, 19), a(15, 18),
a(13, 18), a(5, 12), a(9, 15), a(6, 20), a(14, 10), a(9, 18),
a(12, 15), a(6, 11)),
Arrays.asList(a(4, 16), a(2, 6), a(7, 4), a(15, 9), a(15, 15), a(6, 13),
a(14, 10), a(8, 9), a(7, 1), a(11, 6), a(2, 6), a(11, 1), a(11, 0),
a(4, 4), a(3, 20), a(9,6), a(13,13), a(1,3), a(2,7),
a(4,10), a(14,18), a(2,9), a(0,3), a(12,6), a(14,10), a(9,9),
a(15,12), a(3,14), a(15,6), a(7,2), a(14,15), a(9,7),
a(1,12), a(13,15), a(0,9), a(15,20), a(6,6), a(12,0), a(5,13),
a(7,17), a(15,15), a(5,10), a(14,14), a(1,3), a(13, 8), a(9,19), a(12,9), a(15,4), a(0,5), a(8,16))));
}
private static List<Integer> a(int i, int j) {
return Arrays.asList(i, j);
}
Expected output for this is :
[22, 50, 37, 3, 2, 31, 8, 33, 37, 19, 50, 19, 19, 50, 3, 30, 9, 50, 50, 50, 3, 50, 50, 17, 8, 30, 3, 33, 3, 37, 5, 30, 43, 8, 50, 1, 45, 17, 34, 12, 2, 50, 5, 50, 14, 3, 17, 3, 50, 14]
Based on soltion provided by Mohaned El-haddad I tried below code, but this code is giving wrong output as [3, 2, 3, 3, 1, 2, 3, 8, 3, 8, 5, 5, 9, 8, 14, 17, 17, 17, 19, 19, 19, 30, 30, 30, 3, 33, 14, 37, 37, 37, 12, 31, 45, 34, 50, 22, 50, 50, 3, 33, 50, 50, 50, 50, 50, 43, 50, 50, 50, 50] for my Additional Test case.
public static List<Integer> process(List<List<Integer>> rectangles, List<List<Integer>> points) {
int[] freq_arr = new int[101];
rectangles.sort((r1, r2) -> r2.get(0) - r1.get(0));
points.sort((p1, p2) -> p2.get(0) - p1.get(0));
int idx = 0;
int N = rectangles.size();
List<Integer> list = new ArrayList<>();
for (List<Integer> point : points) {
while (idx < N && rectangles.get(idx).get(0) >= point.get(0)) {
add(freq_arr, rectangles.get(idx).get(1));
idx++;
}
list.add(calc(freq_arr, point.get(1)));
}
return list;
}
private static int calc(int[] freq_arr, int b) {
int count = 0;
for (int i = b; i < freq_arr.length; i++) {
count += freq_arr[i];
}
return count;
}
private static void add(int[] freq_arr, int y) {
freq_arr[y]++;
}
Your curreent solution has TC O(n * m) where n and m are the length of the rectangle array and points array.
Here's a possible improvement in terms of TC:
- Create a sorted map with keys being the
xcoordinates of the rectangles and the values an array of theycoordinates that have thosex. - Make sure the map is sorted increasing on the keys.
- Iterate over the points. For each point do the following:
- Find the minimum key (x coordinate) that covers the x coordinate of that point. This operation is logarithmic since the map is sorted. You can be sure that all the keys after this key also cover the point.
- Check the values of all keys greater than or equal to the found key. These are the y values. If they satisfy the condition, add them to your result.
To improve your algorithm: Also sort the values of the map. This way, finding the minimum satisfying y coordinate also takes logarithmic time and you don't need to check the rest. You can just subtract that index from the value array length.
Let me explain a simple solution by using only sorting, frequency array and 2 pointers.
-
For a point (a,b) to lies inside a rectangle(x1,y1,x2,y2) 4 conditions must be met.
- a >= x1
- a <= x2
- b >= y1
- b <= y2
since in this problem x1=0 and y1=0 and a>=0
then condition 1 and 3 are always satisfied.
Now we need to check for each query point how many rectangles satisfy the two remaining conditon.
lets rename x2 to x and y2 to y since the other value are always zero.
1) x >= a
2) y >= b
Take a look at the constraints you will find that MAX_Y = 100 we will use this to check if the second condition is met.
how can we solve this easly ?
lets create an freq_arr[MAX_Y+1];
when we want to add a new rectangle(x,y) to our freq_arr we will do
void add(freq_arr,y){
freq_arr[y]++;
}
when have a point(a,b)
when we want to query how many rectangle have their y >= b we can do this:
void calc(freq_arr,b){
int count =0;
for(int i = b;i<=MAX_Y;i++)count+=freq_arr[i];
return count;
}
This way we can check if the condition(2) is satisfied in O(MAX_Y).
let's do a little trick that will help us make sure the condition(1) is always satisfied
-
sort all rectangles in decreasing order of x.
-
sort all point in decreasing order of x.
-
let's create a pointer to rectangles array and called it rectangle_idx_to_be_added and initalize it with zero.
-
let's iterate over points array to answer each point separately.
for(auto point : points){ // add all rectangles that have x>=a to freq_arr while(rectangle_idx_to_be_added <N && rectangles[rectangle_idx_to_be_added].x >= point.a){ add(freq_arr,rectangles[rectangle_idx_to_be_added].y); rectangle_idx_to_be_added++; } // at this point all the points in the the freq_arr have x>=a // and all we need to check is how many y >= b // which we can do easily using the freq_arr ans[point.query_idx] = calc(freq_arr,point.b); }
Time complexity O(NlogN + N*MAX_Y)
NlogN for sorting and N*MAX_Y for answering the queries