Finding pair of big-small points from a set of points in a 2D plane

Question

The following is an interview question which I've tried hard to solve. The required bound is to be less than O(n^2). Here is the problem:

You are given with a set of points S = (x1,y1)....(xn,yn). The points are co-ordinates on the XY plane. A point (xa,ya) is said to be greater than point (xb,yb) if and only if xa > xb and ya > yb. The objective is the find all pairs of points p1 = (xa,ya) and p2 = (xb,yb) from the set S such that p1 > p2.

Example:

Input S = (1,2),(2,1),(3,4)

Answer: {(3,4),(1,2)} , {(3,4),(2,1)}

I can only come up with an O(n^2) solution that involves checking each point with other. If there is a better approach, please help me.

Answer 1

I am not sure you can do it.

Example Case: Let the points be (1,1), (2,2) ... (n,n).

There are O(n^2) such points and outputting them itself takes O(n^2) time.

Answer 2

I am assuming you actually want to count such pairs.

Sort descendingly by x in O(n log n). Now we have reduced the problem to a single dimension: for each position k we need to count how many numbers before it are larger than the number at position k. This is equivalent to counting inversions, a problem that has been answered many times on this site, including by me, for example here.

The easiest way to get O(n log n) for that problem is by using the merge sort algorithm, if you want to think about it yourself before clicking that link. Other ways include using binary indexed trees (fenwick trees) or binary search trees. The fastest in practice is probably by using binary indexed trees, because they only involve bitwise operations.

If you want to print the pairs, you cannot do better than O(n^2) in the worst case. I would be interested in an output-sensitive O(num_pairs) algorithm too however.