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;
}
}