Check how many rectangles cover a point

Question

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

Answer 1

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:

1. 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.
2. Make sure the map is sorted increasing on the keys.
3. 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.

Answer 2

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.
  

  1. a >= x1
  2. a <= x2
  3. b >= y1
  4. 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

1. sort all rectangles in decreasing order of x.

2. sort all point in decreasing order of x.

3. let's create a pointer to rectangles array and called it rectangle_idx_to_be_added and initalize it with zero.

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

Answer 3

I think you could simplify the problem by using special data structures, e.g. TreeSet.

Another obvious way is that you have to create a data structure, to efficiently retrieve required points.

I offer to use TreeSet to efficiently retrieve all points within a given range and then use two HashMap to efficiently receive points by their coordinates.

public class Main {

    public static void main(String[] args) {
        List<List<Integer>> inp1 = List.of(List.of(1, 2), List.of(2, 3), List.of(1, 5));
        List<List<Integer>> points = List.of(List.of(1, 1), List.of(1, 4));
        List<Integer> counts = process(inp1, points);
        System.out.println(counts); // [3, 1]
    }

    private static final class Point {

        private final int x;
        private final int y;
        private int count;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    public static List<Integer> process(List<List<Integer>> inp1, List<List<Integer>> inp2) {
        return processPoints(
                inp1.stream()
                    .map(i -> new Point(i.get(0), i.get(1)))
                    .collect(Collectors.toList()),
                inp2.stream()
                    .map(i -> new Point(i.get(0), i.get(1)))
                    .collect(Collectors.toList()));
    }

    private static List<Integer> processPoints(List<Point> rectangles, List<Point> points) {
        NavigableSet<Integer> uniqueSortedX = getSortedByX(points);
        NavigableSet<Integer> uniqueSortedY = getSortedByY(points);
        Map<Integer, Map<Integer, Point>> map = getMap(points);

        for (Point rectangle : rectangles) {
            for (int x : uniqueSortedX.subSet(0, true, rectangle.x, true)) {
                if (!map.containsKey(x))
                    continue;

                Set<Integer> ys = new HashSet<>(uniqueSortedY.subSet(0, true, rectangle.y, true));
                ys.retainAll(map.get(x).keySet());

                for (int y : ys)
                    if (map.get(x).containsKey(y))
                        map.get(x).get(y).count++;
            }
        }

        return points.stream()
                     .map(point -> point.count)
                     .collect(Collectors.toList());
    }

    private static NavigableSet<Integer> getSortedByX(List<Point> points) {
        NavigableSet<Integer> unique = new TreeSet<>();

        points.stream()
              .map(point -> point.x)
              .forEach(unique::add);

        return unique;
    }

    private static NavigableSet<Integer> getSortedByY(List<Point> points) {
        NavigableSet<Integer> unique = new TreeSet<>();

        points.stream()
              .map(point -> point.y)
              .forEach(unique::add);

        return unique;
    }

    private static Map<Integer, Map<Integer, Point>> getMap(List<Point> points) {
        Map<Integer, Map<Integer, Point>> map = new HashMap<>();
        points.forEach(point ->
                map.computeIfAbsent(point.x, x -> new HashMap<>()).put(point.y, point));
        return map;
    }

}

Answer 4

I'm not specialist in Java, that's why I can't help you with code, but I will try to explain an algorithm to solve the issue.

Due to amount of data you need to reduce the number of comparisons. This can be achieved by special hierarchical structure of nested rectangles.

From the example on the top of your issue with rectangles [[1,2], [2,3], [1,5]] you will have on the top level of such structure two branches:

[2,3] and [1,5]

on the second layer [2,3] will have a child [1,2]

[1,5] will not have any children

As a result, when you will check every point, you will start from the top and will work with only branches that include the point.

On the big amount of data you will have much better performance by discarding unnecessary branches.

To improve performance further, you will need to store in every node the depths of child branches.