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

`O(n)`

by using a set implemented with a hash tablecan'tafford to put in all pairs? Also, re-reading your question, it doesn't make much sense. Givena setof 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"?