RSS Feed

techInterview Discussion

You are given N points.
Preprocess them such that given any rectangle, we can find the  number points that lie inside the rectangle in O(log N) time.
Note that we need just the number of points not which points lie inside.
Can we do the pre-processing in O(N^2) time? What do we do in that pre-processing?
I could come up with O(N^4) pre-processing. Anything better?

First solve the simple case where the points have integer coordinates between 1 and n. To prepare, compute the number of points in each rectangle with a corner at (1,1) and an opposite corner at a grid point (of which there are n^2). This can be done by computing running sums first horizontally and then vertically.

Now to answer a query for the rectangle ((a,b),(c,d)) where a < c and b < d, return count((1,1),(c,d)) - count((1,1),(a-1,d)) - count((1,1),(c,b-1)) + count((1,1),(a-1,b-1)).

The reduction to this case is straightforward.

d, are you assuming that the rectangles are composed of line segment parallel to the x and y axes?

Sincerely,

Gene Wirchenko

Yes. I don't know how to do arbitrary rectangles.

google "Segment Tree" or "Interval Tree"

d:
But how to move to the real (as opposed to integer) version?

The way to abstract d.'s solution away from integers is, instead of using integers as grid points, use all x/y coordinates present input data. (That is, loop through the inputs remembering all x coords, and use those as your x grid points, etc.)

In C++ish terminology...

have two multimaps with the key as X and Y co ordinates respectively, and the value as the index of the corresponding point.

Then you can use upper_bound, lower_bound and set_union, and do it in logarithmic time.