879202. Hashing for pair - 2
Easy
Hashing for pair - 2
Summary
Given two arrays arr1 and arr2, find all pairs (x, y) where x is from arr1 and y is from arr2 such that x + y = target_sum. The size of the arrays can be large, so a hash-based solution is required.
Detailed Explanation
We can solve this problem using a hash table (HashMap in Java or Python dictionary) to store the elements of arr1 as keys and their indices as values. Then, for each element y in arr2, we check if the target sum minus y exists in the hash table. If it does, then (target_sum - y, y) is a valid pair.
Here's a step-by-step breakdown of the solution:
- Create an empty hash table.
- Iterate through
arr1. For each elementx, addxas a key and its index in the array as the value to the hash table. - Iterate through
arr2. For each elementy, check if the target sum minusyexists as a key in the hash table. - If it does, then
(target_sum - y, y)is a valid pair. Add it to the result list.
Time complexity: O(n + m), where n and m are the sizes of arr1 and arr2, respectively. Space complexity: O(n), as we need to store all elements of arr1.
Optimized Solutions
Here are optimized solutions in various languages:
Java
import java.util.HashMap;
import java.util.Map;
public class HashingForPair {
public static void findPairs(int[] arr1, int[] arr2, int targetSum) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr1.length; i++) {
map.put(arr1[i], i);
}
for (int j = 0; j < arr2.length; j++) {
if (map.containsKey(targetSum - arr2[j])) {
System.out.println("Pair: (" + (targetSum - arr2[j]) + ", " + arr2[j] + ")");
}
}
}
}