CareerCup

This will be O(n), but could be done in parallel by distributing the list of rectangles to multiple nodes.

Algo,

You need to check only 4 positions for this. Find nearest left, right, top and bottom edge of the rectangles who overlaps the point P. then calculate then minArea(left , right, top bottom) rectangle gives you the answer.

Algorithm will take constant time if you can find those edges in constant time else it slips to O(n) for finding part overtime.

There's no way to do this in less than O(n) given what you've said and no extra constraints.

hprem991,
Unclear from your algo is how would you conclude the nearest edges without visiting all the rectangles. If some rectangles aren't checked, how can we conclude none of those could be the answer?

In what aspect they wanted the optimization? Can we assume that there a lot of queries and we need to do some preprocessing, or we don't have space to store all rectangles, so we need some online algorithm? Could you clarify. I see that this is telephonic interview

I think we can do it in O(log n) using interval trees. Lets say the given point is (x,y). Lets say, the positions of lower-left (xL, yL) & upper-right (xH, yH) corners of each rectangle are given. We will create two interval trees. Each node of first interval tree (say treeX) will have pair (xL, xH) corresponding to each rectangle. Similarly, each node of second interval tree (say treeY) will have pair (yL, hH) corresponding to each rectangle. In first pass (which is O(log n)), we will use treeX to get all the rectangles for which (xL < x < xH). In second pass (which is also order O(log n)), we will use treeY to get the minimum rectangle that contains (x,y).

Could anyone please elaborate what the question is asking?
Do we need to find the rectangle with the smallest area that contains a given point? Or we need to find the rectangle that contains a point and the area formed by one of four vertices of the rectangle and this point is minimal?

perhaps dynamic programming was intended?
If area and density are bounded, repeated rectangles are assumed and you can somewhat optimized (since there are "billions" of rectangles)

divide and conquer?
merge step would be to find intersecting rectangle of 2 min overlapping rectangles?