I have a list of points `[[1,2], [2,3], [1,5]]`

each point represents a rectangle of dimension `[0,0], [x, 0], [0, y], [x,y]`

. Here for example for `[1,2], x =1 and y = 2`

Now I have another list of points `[[1,1], [1,4]]`

. Now my task is to check how many reactangles 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.

**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 the solution?

```
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);
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));
int k1 = startsFrom(values, y);
if (k1 != -1) {
count += values.size() - k1;
}
}
result.add(count);
}
}
return result;
}
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;
}
```

6

## 1 Answer

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
`x`

coordinates of the rectangles and the values an array of the`y`

coordinates that have those`x`

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

6

Isn’t this the line sweep algo?

– SomeoneWhat I proposed isn’t the line sweep algo. I’m thinking that if we were dealing with one dimension, we could use the line sweep algo. But since we need to check also the y coordinates it wouldn’t work. But I’m not 100% sure.

– user1984hey @Someone I skimmed the article you posted. I had a somewhat different view of the line sweep algorithm. You are correct. What I’m proposing has some fundamental similarities with the line sweep algo.

– user1984`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.`

Once I get the minimum key, how can I get the index of that key in map to iterate for other remaining keys. Because in Java, map has no indexO method. Same applies to map values also.–If that’s the case, then don’t use a map at all. Create a simple array of instances of a class that has an int for x and another array for the ys that have that x in a rectangle. Then sort the array with a custom comparator based on the x values of the class instances. Now, you can binary search for the minimum index with an x that covers your point and can index the rest too. You could also use an array of array instead of array of class. In this approach, you can say that the first element of the inner arrays is the x coord and the rest the y coords that have such an x. Hope that makes sense

– user1984

What do you mean by

?`time out errors`

Don’t quote me on this, but I think we can use line sweep.

@PM77-1, my code time complexity is O(N^2) as my input range is very large, it is taking very large time, which is not effiecient. I am looking for a point where I can break the inner loop or some other approach to reduce the time complexity.

@Someone, can you explain what is line sweep.

I see there are requests to close my post, is there something wrong with my question?