Matching Nuts and Bolts Problem

Matching nuts and bolts problem can be stated as follows: “Given a collection of n nuts of distinct sizes and n bolts such that there is a one-to-one correspondence between the nuts and the bolts, find for each nut its corresponding bolt.” We can only compare nuts to bolts i.e., we can neither compare nuts to nuts nor bolts to bolts.

If we could compare nuts to nuts and bolts to bolts, we could simply sort both nuts and bolts separately and pair off the nuts and bolts in matching positions. However, since comparing identical items is not allowed, this problem appears to be harder than sorting. As we will soon see, it can indeed be reduced to sorting.

The brute-force solution would be to compare each nut with all bolts to find the matching bolt and can be implemented in O(n2). In fact, we can do better than n2 by using a randomized algorithm similar to quicksort.

Suppose we choose a nut and partition all bolts in {1…n}, by comparing with this nut, into three intervals : {1…i-1}, {i}, {i+1, n} such that each bolt in {1, i-1} is smaller, bolt i matches and each bolt in {i+1, n} is larger than the chosen nut. This procedure is similar to the partition procedure used in quicksort and can be implemented in O(n). Now, we can use the matching bolt to partition all nuts in three intervals in a similar manner so that the nut i and bolt i match. We have reduced the problem of finding matchings in the interval {1…n} into two smaller subproblems: finding matchings in the intervals {1…i-1} and {i+1…n}.

If at each step, we choose the nut (to partition the bolts) randomly, we will get similar performance guarantees as quicksort i.e., randomized O(n log n) time.


Take a look at C++ implementation.
Reference: The Algorithm Design Manual by Steven S. Skiena

3 thoughts on “Matching Nuts and Bolts Problem

  1. hi kartik kukreja, You have i -= 1 in your code. Will this lead to endless loop? Can you finish the code Partition(bolts[lo…hi], nut)? It would be better if it is in java. Thank you!

    • No, it wouldn’t lead to an infinite loop. There is only 1 matching bolt for a given nut. Once we find it, we swap it with the last bolt. Now, since this swapped bolt also needs to be checked, we decrease i by 1 and then for loop increases i by 1, so that i stays at the same place and we check this swapped bolt.

      The code for Partition(bolts[lo…hi], nut) is complete. I think you are asking for the code for Partition(nuts[lo…hi], bolt). That code is exactly the same, with nuts instead of bolts and bolt instead of nut. In fact, in the C++ implementation, I’ve replaced these two functions with a template.

      Please look at the C++ implementation provided at the end of the post. It should be easily readable to a java coder and it has ample comments to explain what it is doing.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s