Find a unique pair of pairs

3
votes

Given a set of n pairs of integers, is there a fast way to determine if there exists two pairs (x_1,y_1) and (x_2, y_2) in the set such that x_1 != x_2 and y_1 != y_2?

For example, {(0,1), (0,2), (2,1), (3,2)} has {(0,2), (2,1)}. However {(1,0), (2,0), (3,0) does not have any satisfying pair of pairs.

A naive approach just tries all pairs of pairs. There are O(n^2) of these. Can you get something closer to linear time?

If it speeds things up we can assume the pairs are stored as pointers from an array in sorted order (by then first then second coordinate).

4
algorithm
You'd better add what you have done. – herohuyongtao
@herohuyongtao You can try all possible pairs but that is O(n^2) time. I would like to know if you can get something closer to linear time. – marshall
You can get O(n) by using a set implemented with a hash table – loopbackbee
@goncalopp What are you putting in the set? You can't afford to put in all pairs of pairs. – marshall
@marshall simply putting each pair in the set. Did you mean you can't afford to put in all pairs? Also, re-reading your question, it doesn't make much sense. Given a set of n pairs of integers, there exist two different pairs if the size of the set is >1 ... Did you mean a "group", or a "list"? – loopbackbee

4 Answers

2
votes

You can use following O(n) algorithm. To simplify the notation let me call (x,y) a point.

Note that such pair of points does not exist only when all points lay on one line parallel to the axis. Determine this line by first two points and then, for each new point, check if it lays on the same line or not.

1
votes

If the first two pairs are (x1, y1) and (x1, y2) [y1 != y2], then from the remaining list of pairs, if you find any x != x1, its corresponding y shall either not be equal to y1 or not equal to y2.

0
votes

That depends a bit on the language you use, but in Java you could create a Pair class, and override equals and hashcode. Make equals return true if either x1==x2 OR y1==y2. Then just create a HashSet<Pair> and add all of your pairs. What will be in the set at the end will be all the distinct pairs, according to your definition of equality.

0
votes

Second attempt:

You will need: 1 graph, and 1 integer i.

Iterate over your pairs, putting them into a directed graph as you go, such that for every (x, y) there is a directed edge x -> y. After adding an edge to the graph, check both vertices:

If the x and y vertices both have degree zero, increment i. Otherwise, for each vertex that has degree exactly 2, decrement i.

As long as i > 0 there exists a pair of pairs that satisfy your condition.