Problem

Given n Nuts and n Bolts of different sizes, with a one-to-one mapping between nuts and bolts, write an algorithm to find all matches between nuts and bolts. You are allowed to compare only nuts with bolts, and not nuts with nuts or bolts with bolts.

Note: This problem can also be framed as- Given ‘n’ keys and ‘n’ locks. There is one-to-one mapping between keys and locks, means each lock has a specific key and can be unlocked using that key only. Write an algorithm to find all matches between keys and locks.

You are allowed to compare only nuts with bolts (or keys with locks), nuts with nuts or bolts with bolts comparisons are not allowed.

Examples

 Input:
nuts:  ['@', '#', '$', '%', '^', '&']
bolts: ['$', '%', '&', '^', '@', '#']

Output:
Nuts:  ['@', '#', '$', '%', '^', '&']
Bolts: ['@', '#', '$', '%', '^', '&']

Solution

Method 1 - Naive

Compare each nut (or key) with all the bolts (or locks) until a match is found.

Code

Java
public class Solution {

    public static void matchPairs(char[] nuts, char[] bolts) {
        for (int i = 0; i < nuts.length; i++) {
            char nut = nuts[i];
            for (int j = 0; j < bolts.length; j++) {
                if (nut == bolts[j]) {
                    swap(bolts, i, j);
                    break;
                }
            }
        }
        System.out.println("Matched nuts and bolts are:");
        System.out.println("Nuts:  " + Arrays.toString(nuts));
        System.out.println("Bolts: " + Arrays.toString(bolts));
    }

    // Swap method to exchange elements in the array
    public static void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        char[] nuts = {'@', '#', '$', '%', '^', '&'};
        char[] bolts = {'$', '%', '&', '^', '@', '#'};
        
        matchPairs(nuts, bolts);
    }
}
Python
def match_pairs(nuts, bolts):
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]  # Swap elements in the array

    for i in range(len(nuts)):
        nut = nuts[i]
        for j in range(len(bolts)):
            if nut == bolts[j]:
                swap(bolts, i, j)
                break

    print("Matched nuts and bolts are:")
    print("Nuts:  ", nuts)
    print("Bolts: ", bolts)

# Example usage
if __name__ == "__main__":
    nuts = ['@', '#', '$', '%', '^', '&']
    bolts = ['$', '%', '&', '^', '@', '#']
    
    match_pairs(nuts, bolts)

Method 2 - Using map

Store each nut as a key and its position as the value in a HashMap. Then, for each bolt, check the HashMap for a matching nut and place it in the correct position.

Code

Java
public class Solution {

    public static void matchPairs(char[] nuts, char[] bolts) {
        // Create a HashMap for nuts, with nut as key and its position as value
        HashMap<Character, Integer> nutMap = new HashMap<>();
        for (int i = 0; i < nuts.length; i++) {
            nutMap.put(nuts[i], i);
        }

        // For each bolt, check for the nut in the HashMap
        for (int i = 0; i < bolts.length; i++) {
            char bolt = bolts[i];
            if (nutMap.containsKey(bolt)) {
                nuts[i] = bolt;  // Place the matching nut in the correct position
            } else {
                System.out.println("For bolt " + bolt + " no matching nut is present.");
                return;
            }
        }

        System.out.println("(Hash Map) Matched nuts and bolts are:");
        System.out.println("Nuts:  " + Arrays.toString(nuts));
        System.out.println("Bolts: " + Arrays.toString(bolts));
    }

    public static void main(String[] args) {
        char[] nuts = {'@', '#', '$', '%', '^', '&'};
        char[] bolts = {'$', '%', '&', '^', '@', '#'};
        
        matchPairs(nuts, bolts);
    }
}
Python
def match_pairs(nuts: List[str], bolts: List[str]) -> None:
    # Create a dictionary for nuts, with nut as key and its position as value
    nut_map = {nut: i for i, nut in enumerate(nuts)}

    # For each bolt, check for the corresponding nut in the dictionary
    for i in range(len(bolts)):
        bolt = bolts[i]
        if bolt in nut_map:
            nuts[i] = bolt  # Place the matching nut in the correct position
        else:
            print(f"For bolt {bolt} no matching nut is present.")
            return

    print("(Hash Map) Matched nuts and bolts are:")
    print("Nuts:  ", nuts)
    print("Bolts: ", bolts)

    # Example usage
if __name__ == "__main__":
    nuts = ['@', '#', '$', '%', '^', '&']
    bolts = ['$', '%', '&', '^', '@', '#']

    match_pairs(nuts, bolts)

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - Partition logic

We can solve this problem using the QuickSort-based partition approach:

  1. Partition: Use a nut as a pivot to partition the bolts, then use the matched bolt to partition the nuts.
  2. Recursively Apply: Recursively apply the partitioning to match the entire set of nuts and bolts.

Code

Java
public class Solution {

    private static void matchPairs(char[] nuts, char[] bolts, int low, int high) {
        if (low < high) {
            // Choose the last element of nuts as pivot to partition bolts
            int pivotIndex = partition(bolts, low, high, nuts[high]);
            // Partition nuts with the matched bolt
            partition(nuts, low, high, bolts[pivotIndex]);

            // Recursively apply the partitioning to the remaining elements
            matchPairs(nuts, bolts, low, pivotIndex - 1);
            matchPairs(nuts, bolts, pivotIndex + 1, high);
        }
    }

    private static int partition(char[] array, int low, int high, char pivot) {
        int i = low;

        // Partition the array based on the pivot
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                swap(array, i, j);
                i++;
            } else if (array[j] == pivot) {
                swap(array, j, high);
                j--;
            }
        }
        swap(array, i, high); // Restore the pivot element to its position
        return i;
    }

    private static void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        char[] nuts = {'@', '#', '$', '%', '^', '&'};
        char[] bolts = {'$', '%', '&', '^', '@', '#'};

        matchPairs(nuts, bolts, 0, nuts.length - 1);

        System.out.println("Matched nuts and bolts:");
        System.out.println("Nuts:  " + Arrays.toString(nuts));
        System.out.println("Bolts: " + Arrays.toString(bolts));
    }
}
Python
class Solution:
    def match_pairs(self, nuts: List[str], bolts: List[str]) -> None:
        def partition(arr: List[str], low: int, high: int, pivot: str) -> int:
            i = low
            for j in range(low, high):
                if arr[j] < pivot:
                    arr[i], arr[j] = arr[j], arr[i]
                    i += 1
                elif arr[j] == pivot:
                    arr[j], arr[high] = arr[high], arr[j]
                    j -= 1
            arr[i], arr[high] = arr[high], arr[i]
            return i

        def match_pairs_util(nuts: List[str], bolts: List[str], low: int, high: int) -> None:
            if low < high:
                pivot_index = partition(bolts, low, high, nuts[high])
                partition(nuts, low, high, bolts[pivot_index])
                match_pairs_util(nuts, bolts, low, pivot_index - 1)
                match_pairs_util(nuts, bolts, pivot_index + 1, high)
        
        match_pairs_util(nuts, bolts, 0, len(nuts) - 1)

# Example usage
sol = Solution()
nuts = ['@', '#', '$', '%', '^', '&']
bolts = ['$', '%', '&', '^', '@', '#']
sol.match_pairs(nuts, bolts)

print("Matched nuts and bolts:")
print("Nuts:  ", nuts)
print("Bolts: ", bolts)

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(log n)