Nuts & Bolts Problem (Lock & Key problem)

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.
Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

Other way of asking this problem is, given a box with locks and keys where one lock can be opened by one key in the box. We need to match the pair.

Logic

• first performs a partition by picking last element of bolts array as pivot,
• rearrange the array of nuts and returns the partition index ‘i’ such that all nuts smaller than nuts[i] are on the left side and all nuts greater than nuts[i] are on the right side.
• Next using the nuts[i] we can partition the array of bolts. This operation also makes nuts and bolts array nicely partitioned.
• Now we apply this partitioning recursively on the left and right sub-array of nuts and bolts.

As we apply partitioning on nuts and bolts both so the total time complexity will be Θ(2*nlogn) = Θ(nlogn) on average.

CODE

    private static void matchPairs(char[] nuts, char[] bolts, int low, int high)

    {

        if (low < high)

        {

            // Choose last character of bolts array for nuts partition.

            int pivot = partition(nuts, low, high, bolts[high]);

            // Now using the partition of nuts choose that for bolts

            partition(bolts, low, high, nuts[pivot]);

            // Recur for [low...pivot-1] & [pivot+1...high] for nuts and bolts array.

            matchPairs(nuts, bolts, low, pivot-1);

            matchPairs(nuts, bolts, pivot+1, high);

        }

    }