Finding the minimum element in a given range greater than a given number

Question

We are given N (N <= 10⁶) points on a 2D plane and an integer D (N <= 10⁶), we want to find two points p1,p2 (p2 to the right of p1) such that the difference between p1.y and p2.y is at least D and p2.x - p1.x is minimized.

The x and y axis are in the range 0..10⁶

This is a problem from a USACO past contest.

Here is my attempt to solve it:
MAXY = The maximum y axis among the N points.
Suppose we know p1, then we can find p2 quite easily; by taking all the points which have their y-axis in the range p1.y+D to MAXY or in the range 0 to p1.y-D and take the point which has the smallest x-axis greater than p.x. This will be the best choice for p2.

But as we don't know p1, we will have to try all points for p1 and so finding the best choice for p2 should be done efficiently.

I used a segment tree for that. Every node in the tree will store all the points in the corresponding range in sorted order of x-axis. While querying, if a node falls in the query range then we binary search on the array for p1.x and return the smallest element greater than it.

For every choice of p1, we query the tree twice with the ranges 0,p1.y-D and p1.y+D,MAXY and take the best of the two points returned.

The building of the tree can be done in O(NlogN) time. Every query will take O(logN*logN) time, and we make N queries, so the total time taken is (Nlogn*logn) which might not run within the time limits of 2 seconds. (10⁶*20*20). Also the memory taken will be O(NlogN) which is about 80 mb (100000*20*4 kb) which is too much as the limit is 64 mb.

How can we do the queries faster and using lesser space?

Answer 1

It can be done much easier.

Suppose you have two copies of the array: one sorted by Y-axis and another by X-axis. Now you'll iterate through the Y-sorted array and for each point (let name it cur) you should binary search an appropriate point (with the smallest p2.x - p1.x) in the X-sorted array. In case of binary search will find the same point or the point with Y-coordinate less than cur+D you should just delete that point from X-sorted array (we'll never need that point in X-sorted array again because we only increase Y-coordinate) and run binary search again. The answer will be the smallest of the binary search results.

As we need fast timing we should erase points from array quickly. It can be done by using binary tree - it can erase any node in O(logN) time and can do binary search in O(logN) time. As you delete each node from the tree only once and it takes O(logN + logN) time - total time will be O(N * logN). Preprocesssing time is O(N * logN) too. Also the memory taken will be O(N).

By the way your solution is also appropriate because actual N is 10^5 not 10^6. Which allows your solution to keep timing below 2 seconds, and to use less than 20MB of memory.

Answer 2

How about just do Sort & Scan.

Sort by x since you want to find the minimum difference by x. It take O(N logN) time and in place.

Maintain two index i and j from the head of x.

The faster goes first, find the position of |P[i].y - P[j].y| > D

and the X = |P[i].x - P[j].x| is your first available choice.

Then updating X by moving the to index forward. Try P[i+1], scan from P[i+2] as P[j] and increase until |P[i].x - P[j].x| >= X. If there is an available new X, set this as X.

This might make do lot of compare at first. But since you updating your X, somehow will make your compare range shrinking.