CODEWITHSUNDEEP
algorithm
marshall
marshall

Reputation: 2483

Find a unique pair of pairs

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

Upvotes: 3

Views: 829

Answers (4)

Ziggy
Ziggy

Reputation: 22375

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.

Upvotes: 0

Łukasz Kidziński
Łukasz Kidziński

Reputation: 1623

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.

Upvotes: 2

Irene Papakonstantinou
Irene Papakonstantinou

Reputation: 397

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.

Upvotes: 0

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

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.

Upvotes: 1

Related Questions