PROBLEM DESCRIPTION
Given two unsorted arrays A of size N and B of size M of distinct elements, the task is to find all pairs from both arrays whose sum is equal to X.
Note: All pairs should be printed in increasing order of u. For eg. for two pairs (u1,v1) and (u2,v2), if u1 < u2 then (u1,v1) should be printed first else second.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public pair[] allPairs(long A[], long B[], long N, long M, long X) {
// Create a HashSet to store elements from array A
Set<Long> set = new HashSet<>();
// Add elements from array A to the HashSet
for(int i=0; i<N; i++)
set.add(A[i]);
// Create an ArrayList to store pairs that satisfy the condition
List<pair> list = new ArrayList<>();
// Iterate through array B
for(int i=0; i<M; i++){
// Check if there exists an element in array A such that their sum equals X
if(set.contains(X-B[i])){
// If such an element exists, add the pair (X-B[i], B[i]) to the list
list.add(new pair(X-B[i], B[i]));
}
}
// Convert the list to an array of pairs
pair[] res = new pair[list.size()];
for(int i=0; i<list.size(); i++)
res[i] = list.get(i);
// Sort the array of pairs in increasing order of the first element of each pair
Arrays.sort(res, (a, b) -> (int) a.first - (int) b.first);
return res;
}
}
ANOTHER WAY TO CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public pair[] allPairs(int x, int arr1[], int arr2[]) {
int n = arr1.length;
int m = arr2.length;
// create set using arr2
Set<Integer> set = new HashSet<>();
for(int i=0; i<m; i++)
set.add(arr2[i]);
// list of pairs with sum x
List<pair> list = new ArrayList<>();
// sort the first array so that we always get the smallest first element
Arrays.sort(arr1);
// iterate over the first array
for(int i=0; i<n; i++){
// avoid repeating elements
// if we remove this, it still gets accepted as a solution in gfg
// i think it's because all elements are unique in the test cases
if(i > 0 && arr1[i] == arr1[i-1])
continue;
// first element candidate
int a = arr1[i];
// second element needed
int b = x-a;
// check if second element is present in the set (which has elements of arr2)
if(set.contains(b)){
// if it does, add this pair to the result
// since we sorted arr1, `a` will be the least already
list.add(new pair(a, b));
}
}
// covert to array of pairs
pair[] res = new pair[list.size()];
for(int i=0; i<res.length; i++)
res[i] = list.get(i);
return res;
}
}
UPDATE
The requirement in this problem seems to have changed. So the previous solution does not seem to work any longer. The difference is that, if the second array contains duplicates, we need to consider them multiple times as well. This can easily be incorporated by storing the frequency of numbers in the second array using HashMap (instead of using HashSet like before).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public pair[] allPairs(int x, int arr1[], int arr2[]) {
int n = arr1.length;
int m = arr2.length;
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<m; i++)
map.put(arr2[i], map.getOrDefault(arr2[i], 0) + 1);
List<pair> list = new ArrayList<>();
Arrays.sort(arr1);
for(int i=0; i<n; i++){
int a = arr1[i];
int b = x-a;
if(map.containsKey(b)){
int times = map.get(b);
for(int k=0; k<times; k++){
list.add(new pair(a, b));
}
}
}
pair[] res = new pair[list.size()];
for(int i=0; i<res.length; i++)
res[i] = list.get(i);
return res;
}
}