CODEWITHSUNDEEP
algorithmsortingcomplexity-theory
Jacek Trociński
Jacek Trociński

Reputation: 920

finding matching pairs in two sets in O(nlogn)

There is a set A and set B of size n, for every card in set A there is a corresponding card in set B.

Describe a more efficient algorithm with an average case complexity of O(nlogn) tests to find the matching pairs. Prove that your algorithm satisfies the desired complexity.

I'm thinking I can just use quicksort to sort each set, that would be nlogn + nlogn, then i would know that the corresponding position in each set were matching pairs. would this be correct? Here is the problem in it's entirety

Each set consists of n cards and for every card in the set A there is a corresponding card in the set B that belong to the same account, and we will refer to these two cards as the matching pair. Each card is a small plastic object containing a magnetic strip with some encrypted number that corresponds to a unique account in the bank. It is required to find all matching pairs. There is a card reader machine such that when two cards, one from set A and one from set B, are inserted in the machine one of its three light indicators turns on; green if the pair matches, red if the account number on A is larger than B, and yellow if the number on B is higher than that of A. However, the card reader cannot compare two cards belonging to the same set.

Upvotes: 3

Views: 4251

Answers (2)

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

Reputation: 26121

You can use card form A set as pivot for quick selection of set B. So you can implement quicksort in this way. So select one card from set A and divide B set to smaller and bigger. If you found matching card in B you can use this card to divide A set. If you not found matching card repeat. If found apply algorithm to smaller and bigger groups in same way as in quicksort. Repeat until you find all matching cards. Complexity is same as for quicksort, so O(n^2) in worst case and O(NlogN) in average.

Example implementation in Erlang:

-module(abcards).

-export([find_pairs/2]).

find_pairs([], _) -> [];
find_pairs(_, []) -> [];
find_pairs([A|As], Bs) ->
  case partitionB(A, Bs, [], [], not_found) of
    {_, _, not_found} -> find_pairs(As, Bs);
    {BLess, BMore, B} ->
      {ALess, AMore} = partitionA(B, As, [], []),
      [{A, B} | find_pairs(ALess, BLess) ++ find_pairs(AMore, BMore) ]
  end.

card_reader(A, B) when A > B -> red;
card_reader(A, B) when A == B -> green;
card_reader(A, B) when A < B -> yellow.

partitionB(_, [], BLess, BMore, Found) -> {BLess, BMore, Found};
partitionB(A, [B|Bs], BLess, BMore, Found) ->
  case card_reader(A, B) of
    red -> partitionB(A, Bs, [B|BLess], BMore, Found);
    green -> partitionB(A, Bs, BLess, BMore, B);
    yellow -> partitionB(A, Bs, BLess, [B|BMore], Found)
  end.

partitionA(_, [], ALess, AMore) -> {ALess, AMore};
partitionA(B, [A|As], ALess, AMore) ->
  case card_reader(A, B) of
    red -> partitionA(B, As, ALess, [A|AMore]);
    yellow -> partitionA(B, As, [A|ALess], AMore)
  end.

Upvotes: 5

Shashank
Shashank

Reputation: 13869

I think it's wise to abuse Partition in this problem.

From Wikipedia:

In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts, those less than a certain element, and those greater than or equal to the element.

Consider the following algorithm.

  1. Pick any card from set A. Let's call it a1.
  2. Partition set B around it using the card reader so that it will break up set B into 3 subsets, those equal to card a1, those less than card a1, and those greater than card a1.
  3. There will always only be one card equal to card a1. Let's call this card b1.
  4. Insert card b1 into a "binary search tree" type thing along with its paired card a1
  5. Pick another card from set A, call it a2.
  6. Compare it with b1 using card reader, if it's less than b1 run a partition on the subset from step (2) for which bk < a1. If it's greater than b1 run a partition on the subset from step(2) for which bk > a2. This is O(n / 2) since we are running partition on a smaller set.
  7. Take card from set B which is equal to a2, call it b2, and insert it into the binary tree from step (4) (insert by comparing to previously matched items from set A).
  8. Repeat for a3, a4, and so on, continuing to break down set B into smaller and smaller sets and using the binary search tree to find the "correct" partitioned set to search for ak in.

Eventually you will get a time complexity like O(n) + 2* O(n / 2) + 2* O(n / 4) + 2* O(n / 8) etc.. Breaking down the problem like this using a binary search tree on every correct pairing, I believe the time complexity will be O(n log n). In the worst case it will obviously be O(n^2) just like quicksort.

Eventually you will end up with a sorted binary tree in which each node contains a pair of matching cards.

Upvotes: 1

Related Questions