CareerCup

Seems like the solution is either a k-d tree or a range tree.

I don't know how the rectangles are represented. I assume it is represented by its four vertices: upper-left -> A(X1, Y1), lower-left -> B(X1, Y2), lower-right -> C(X2, Y2), upper-right -> D(X2, Y1). Then if a point (x, y) in a rectangle, its coordinates should satisfy a relationship:
X1 <= x <= X2 and Y1 <= x <= Y2.

Then we can sort the point list based on x-axis coordinate and y-axis coordinate, and store the two result separately for better search performance. Or if the number of points is large, we can consider using bit map to project each point onto the map.

At last, simply iterate over rectangles list and find if a point in the rectangle with the pre-processed point list or bit map.

Please clarify question. How to find rectangle that contains a point?

Do we have to find the one among the given rectangle which contains all the given list of points or lie on the rectangle itself? or do we have to form a new rectangle with the coordinates of the list of rectangles? please clarify?

/* 
There is a list of rectangles and a list of points in a 2d space. Note that the edge of each rectangle are aligned to XY axis. 
question is how to find rectangles with point or points inside

Note: 0,0 is top, left
*/


import java.util.*;

class Solution {

	public static void main(String[] args) {

		//create a list of rectangles and points
		List<Rectangle> rectangles = new LinkedList<>();
		List<Point> points = new LinkedList<>();

		Point[][] rPoints = {{new Point(0, 0), new Point(10, 10)},
						     {new Point(5, 5), new Point(100, 100)},
						     {new Point(-10, 7), new Point(32, 1001)}};


		for (Point[] p : rPoints) {
			rectangles.add(new Rectangle(p[0], p[1]));
		}

		Point[] pPoints = {new Point(1,1), new Point(-1000, 5), new Point(6, 7)};
		for (Point p : pPoints) {
			points.add(p);
		}

		for (Rectangle r : rectangles) {
			for (Point p : points) {
				System.out.println(r + " contains point: " + p + " :" + r.containsPoint(p));
			}
		}

	}

}

class Rectangle {
	//Note: 0,0 is top, left
	Point topLeft;
	Point bottomRight;

	public Rectangle(Point tl, Point br) {
		topLeft = tl;
		bottomRight = br;
	}

	public boolean containsPoint(Point p) {
		return p.x <= bottomRight.x && 
			   p.x >= topLeft.x && 
			   p.y <= bottomRight.y &&
			   p.y >= topLeft.y;
	}

	public String toString() {
		return "(topLeft: "+topLeft+", bottomRight:"+bottomRight+")";
	}
}

class Point {
	//Note: 0,0 is top, left
	int x;
	int y;

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

	public String toString() {
		return "(x: "+x+", y: "+y+")";
	}

}

// brute force 19 minutes

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class FindEnclosingRectangles {

	static class Point implements Comparable<Point>{
		int x, y;
		
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}

		@Override
		public int compareTo(Point o) {
			//System.out.println(x + "," + y + "\t" + o.x + "," + o.y);
			
			if(o.x != x){
				return x - o.x;
			} else {
				return y - o.y;
			}
		}
	}
	
	static class Rectangle{
		Point pLL, pUR;
		
		Rectangle(Point pLL, Point pUR){
			this.pLL = pLL;
			this.pUR = pUR;
		}
		
		boolean contains(Point p){
			boolean result = p.compareTo(pLL) >= 0 && pUR.compareTo(p) >= 0;
			return result;
		}
	}
	
	List<Rectangle> rectangles;
	
	public FindEnclosingRectangles() {
		rectangles = new LinkedList<Rectangle>();
	}

	private void addRectangle(Rectangle rectangle) {
		rectangles.add(rectangle);
	}

	private List<Rectangle> find(Point point) {
		List<Rectangle> res = new LinkedList<Rectangle>();
		
		for(Rectangle r : rectangles){
			if(r.contains(point)){
				res.add(r);
			}
		}
		
		return res;
	}
	
	  public static void main(String[] args){
		   FindEnclosingRectangles wrapper = new FindEnclosingRectangles();
		
		   wrapper.addRectangle(new Rectangle(new Point(0,0), new Point(4,5)));
		   wrapper.addRectangle(new Rectangle(new Point(1,2), new Point(5,5)));
		   
		   List<Rectangle> res = wrapper.find(new Point(3,4));
		   System.out.println(res.size());
		   
		   res = wrapper.find(new Point(13,4));
		   System.out.println(res.size());
	   }
}

One word: quadtree

Fully working solution

struct Point
{
	Point() :x(-1), y(-1){}
	Point(int x, int y) :x(x), y(y){}
	int x;
	int y;
};

bool isPointInRec(const Rect& rect, const Point& pos)
{
	return(
		rect._leftUpper.y > pos.y &&
		rect._leftUpper.x < pos.x &&
		rect._rightLower.y < pos.y &&
		rect._rightLower.x > pos.x
		);
}

vector<Rect> findRectWithPoint(vector<Rect>& rects, vector<Point>& points)
{
	vector<Rect> result;
	for (const Rect& currRect : rects)
	{
		for (const Point& currPoint : points)
		{
			if (isPointInRec(currRect, currPoint))
			{
				result.push_back(currRect);
			}
		}
	}
	return result;
}


int main(int argc, const char* argv[])
{
		vector<Rect> rectList = { { { 3, 5 }, { 5, 1 } }, 
								  { { 1, 6 }, { 2, 4 } },
								  { { 1, 2 }, { 2, 1 } },
								  { { -3, -3 }, { -1, -5 } }
								};
		vector<Point> points = { { -2, -4 }, { 0, 0 }, { 10, 15 }, { 5, 6 }, { 7, 8 }, { -10, -30 }, { 6, 5 }, { 4, 4 } };

		vector<Rect> res = findRectWithPoint(rectList, points);

}

Here is the C++ version of solution.

Running time is between O(M log N) and O(MN), where M is # of rectangles and N is number of points.
O(MN) is the worst case. I should say just O (MN).
I uses the binary search to find the point with x position within the given rectangle.
If it find it but its y position is not in rectangle it need to search both side, which leads to O(N).

bool bsearch(point *list, int s, int e, rect& target)
{
	if (s > e)
		return false;
	int half = s+ (e-s)/2;
	if (list[half].x >= target.low.x && list[half].x <= target.high.x )
	{
		if (list[half].y >= target.low.y && list[half].y <= target.high.y)
		{
			return true;
		}
		if (bsearch(list, s, half -1, target))
			return true;
		if (bsearch(list, half+1, e, target))
			return true;
	}	
	if (list[half].x < target.low.x)
		return bsearch(list, half+1, e, target);
	else
		return bsearch(list, s, half-1, target);
}

list<rect> find_intersect_rect(rect* input, int len, point * points, int plen)
{
	list<rect> result;
	//sort by x value
	quick_sort(points, 0, plen-1);

	for (int i = 0; i < len; i++)
	{
		if (bsearch(points, 0, plen -1, input[i]))
			result.push_back(input[i]);
	}
	return result;	
}

If we keep track of rectangles overlap, we can exclude significant portions of candidate points each time we consider a new rectangle: if we find that a rectangle does not overlap with a given zone, we can ignore all points there contained.
My Java implementation:

static class Point {

  double x, y;

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

  boolean inRect(Rect rect) {
    return (x >= rect.left && y >= rect.top
            && x <= rect.right && y <= rect.bottom);
  }
}

static class Rect {

  double left, top, right, bottom;

  public Rect(double left, double top, double right, double bottom) {
    this.left = left;
    this.top = top;
    this.right = right;
    this.bottom = bottom;
  }

  Rect mergeWith(Rect rect) {

    if ((left > rect.right) || (rect.left > right)
        || (top > rect.bottom) || (rect.top > bottom)) {
      return null;
    }

    return new Rect(Math.min(left, rect.left), Math.min(top, rect.top),
                    Math.max(right, rect.right), Math.max(bottom, rect.bottom));
  }
}

Map<Rect, List<Point>> findPointsInRects(List<Point> points, List<Rect> rects) {

  Map<Rect, List<Point>> zoneMap = new HashMap<>();
  Map<Rect, List<Point>> resultMap = new HashMap<>();

  for (Rect rect : rects) {

    List<Point> candidatePoints = new ArrayList<>();
    candidatePoints.addAll(points);

    Rect mergedZone = rect; // let us initialize our current rect's zone
    List<Point> mergedZonePoints = new ArrayList<>();

    List<Rect> zonesToMerge = new ArrayList<>();

    for (Rect zone : zoneMap.keySet()) {

      List<Point> zonePoints = zoneMap.get(zone);

      Rect rr = mergedZone.mergeWith(zone);
      if (rr == null) { // disjoint zones -> remove candidates
        candidatePoints.removeAll(zonePoints);
      } else {
        zonesToMerge.add(zone);
        mergedZone = rr;
        mergedZonePoints.addAll(zonePoints);
      }

    }

    List<Point> rectPoints = new ArrayList<>();
    for (Point point : candidatePoints) {
      if (point.inRect(rect)) {
        rectPoints.add(point);
      }
    }
    resultMap.put(rect, rectPoints);

    mergedZonePoints.addAll(rectPoints);

    zoneMap.keySet().removeAll(zonesToMerge);
    zoneMap.put(mergedZone, mergedZonePoints);

  }

  return resultMap;

}