3

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.

uyetch
  • 2,150
  • 3
  • 28
  • 33
  • 1
    Do you need to **count how many such pairs there are** or **print all such pairs**? For the first you can most likely get better than `O(n^2)`, for the latter you cannot. – IVlad Jul 26 '12 at 15:04

3 Answers3

3

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.

ElKamina
  • 7,747
  • 28
  • 43
  • 3
    +1, but the interviewer was probably interested in counting the pairs, not printing them. At least that's a much more interesting problem. – IVlad Jul 26 '12 at 15:05
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.

Community
  • 1
  • 1
IVlad
  • 43,099
  • 13
  • 111
  • 179
0

Why don't you just sort the list of points by X, and Y as a secondary index? (O(nlogn))

Then you can just give a "lazy" indicator that shows for each point that all the points on its right are bigger than it.

If you want to find them ALL, it will take O(n^2) anyway, because there's O(n^2) pairs.

Think of a sorted list, the first one is smallest, so there's n-1 bigger points, the second one has n-2 bigger points... which adds up to about (n^2)/2 == O(n^2)

Yochai Timmer
  • 48,127
  • 24
  • 147
  • 185
  • Yes, but this does not improve on the time complexity, and after giving some serious thought I'd feel like going with the naiive approach which like this one runs in O(n^2) – uyetch Jul 26 '12 at 13:23
  • 1
    @ard , This approach prepares all the pairs in less than O(n^2). This will give you a big advantage if you don't need to actually list them. You can for example do all kinds of searches or queries on this result without ever having to reach O(n^2) – Yochai Timmer Jul 26 '12 at 13:39