Find a unique pair of pairs

Tag: algorithm Author: jerryzhangyin Date: 2013-12-30

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).

You'd better add what you have done.
@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.
You can get O(n) by using a set implemented with a hash table
@goncalopp What are you putting in the set? You can't afford to put in all pairs of pairs.
@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"?

Best Answer

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.

comments:

You mean a line parallel to the x or y axis? After all (1,1), (2,2), (3,3) forms a line.
I love our answers: mathematicians would tear their hair out!
Exactly. I will just update the answer.

Other Answer1

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.

comments:

Yes that sounds right. So really it is linear time. I was wondering, however, if it might even be constant time if you assume the pairs are already placed in an array in sorted order. Can you just look at the first and last pair?
yes this is O(n).

Other Answer2

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.

comments:

What is the time complexity of insertion when you override equals and hashcode?
I think the unstated problem here is how you would actually write hashcode to fulfill the definition.

Other Answer3

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.

comments:

Gosh I hope I'm right!
I guess "degree" here is a pair, (a, b) where a is the number of incident edges, and b is the number of edges leaving the vertex (what's the opposite of incident? Exident?)