CareerCup

This problem can be solved by segment tree and ST(dynamic programming solution).

Hint : Convert Y's in to 1...N ( or Maybe 1.....n , n < N , in case of duplicate Y's ) indexes And Use segment trees !

Am just confused, why is this not the problem equal to finding minimum value of x in the set? If we have a set of records with say 2 columns, then between ymin and y max every entry should come. So simply finding x min should give us the answer.

make a binary tree (inverted, child pointing to parent) with y's in leaf nodes in increasing order left to right, starting with leaf nodes build the tree with node values = min(x) between node leftmost desendent and right most decendent.

My solution was on the lines of Balanced BST. Each Node in BST will hold following values

1. leftYMin (minimum Y value in the left subtree)
2. leftYMax (maximum Y value in the left subtree)
3. rightYMin (minimum Y value in the right subtree)
4. rightYMax (maximum Y value in the right subtree)
5. leftXMin (minimum X value in the left subtree)
5. rightXMin (minimum X value in the right subtree)
6,7. pointers to left , right child

Now, given two Ymin and Ymax, we start at the root node. First we examine the left subtree. Following are the possibilities

1. Ymin and Ymax are within the interval [leftYMin, leftYMax]. In this case we straightaway hold the value of leftXMin in XLeft, i.e. XLeft = leftXMin
2. Ymin and Ymax partially overlap with interval [leftYMin, leftYMax]. In this case we recursively travel down the left child and look for value of XLeft
3. Ymin and Ymax and interval [leftYMin, leftYMax] are disjoint. In this case we discard the left subtree.

Similarly, we examine the right subtree and find the value of XRight.

Our min(X) is min(XLeft, XRight)

At the outset, this solution looks something like interval trees/augmented trees/Range Indexed Trees but I am not sure and I will have to look if that is the case.

PS: For the uninitiated folks who think we just need to find min(X) in the given set, I apologize for not being clear enough. Let me take an example.
Given: an unordered list of (x,y)= (1,28), (5,6), (11,13), (24,37), (8,1), (56,10), (78,19)
and given following value of Ymin, Ymax, the output would be something like
1. Ymin=13, Ymax=19, min(X) = 11
2. Ymin=6, Ymax=37, min(X) = 1

Be A the list of points
Xmin = A[0].x
foundOne = false
for each point p in A
               if p.Y>= Ymin && p.Y <= Ymax 
                        foundOne = true    
                        if p.X < Xmin
                                Xmin=p.X
if !foundOne throw "No points in the given interval"
return Xmin

O(N)

Use a sweep line across the Y-axis. Sort the points by Y coordinate and then while moving the sweep line, keep inserting the x-coodinate into a BST. At any time, the minimum in the BST is the required point.

The solution is pretty easy, unless there is a typo in the question: The condition in the SELECT clause is "Y BETWEEN MIN(Y) AND MAX(Y)", i.e. any X regardless of Y, because all the Y values are between Ymin and Ymax inclusive. Then the problem becomes finding the MIN(X) coordinates. Note that SQL BETWEEN condition is inclusive of the boundary values.

Then you can find the Xmin in O(n) time, just linearly search through the values and then save the Xmin,Y pairs. The problems mentions the duplicates, so instead of a single Xmin,Y coordinate, we need to save all of them. Here is the code in C++11:

vector<const Point> findMinX(vector<Point>& points) {
	unsorted_map<int, vector<Point> >  x_points;
	int min = INT_MAX;
	for (const Point & point: points ) {
		if (p.X < min) min = p.X;
		x_points[pX].emplace_back(point);
	}

	return x_points[min];
}