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 (u_{1},v_{1}) and (u_{2},v_{2}), if u_{1 }< u_{2} then
(u_{1},v_{1}) should be printed first else second.
Example 1:
Input:
A[] = {1, 2, 4, 5, 7}
B[] = {5, 6, 3, 4, 8} 
X = 9 
Output: 
1 8
4 5 
5 4
Explanation:
(1, 8), (4, 5), (5, 4) are the
pairs which sum to 9.
Example 2:
Input:
A[] = {-1, -2, 4, -6, 5, 7}
B[] = {6, 3, 4, 0} 
X = 8 
Output:
4 4 
5 3
Your Task:  
You don't need to read input or print anything. Your task is to complete the function allPairs() which takes the array A[], B[], its size N and M respectively, and an integer X as inputs and returns the sorted vector pair values of all the pairs u,v where u belongs to array A and v belongs to array B. If no such pair exists return empty vector pair.
Expected Time Complexity: O(NLog(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N, M ≤ 10^{6}
-10^{6} ≤ X, A[i], B[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def allPairs(self, A, B, N, M, X):

        # Your code goes here 

    



Solutions:
class Solution:

	def allPairs(self, A, B, N, M, X):
		allpairs = []
		for i in range(N):
			if X - A[i] in B:
				allpairs.append([A[i], X - A[i]])
		return sorted(allpairs)


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		B.sort(reverse=True)
		i = 0
		j = 0
		result = []
		while i != N and j != M:
			if A[i] + B[j] == X:
				result.append([A[i], B[j]])
				i += 1
				j += 1
			elif A[i] + B[j] > X:
				j += 1
			else:
				i += 1
		return result


class Solution:

	def allPairs(self, A, B, N, M, X):
		A = sorted(A)
		B = sorted(B)
		answer = []
		for i in range(N):
			for j in range(-1, -M - 1, -1):
				if A[i] + B[j] == X:
					answer.append((A[i], B[j]))
					break
				elif A[i] + B[j] < X:
					break
		return answer


class Solution:

	def allPairs(self, A, B, N, M, X):
		l = []
		A = list(set(A))
		B = list(set(B))
		A.sort()
		B.sort()
		for i in A:
			l1 = []
			for j in B:
				if i + j == X:
					l1.append(i)
					l1.append(j)
			if len(l1) != 0:
				l.append(l1)
		return l


class Solution:

	def allPairs(self, a, b, n, m, x):
		res = []
		for i in a:
			if x - i in b:
				res.append([i, x - i])
		res.sort()
		return res


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		B.sort()
		l = []
		r = []
		for i in range(N):
			l = []
			for j in range(M):
				if A[i] + B[j] == X:
					l.append(A[i])
					l.append(B[j])
					break
			if len(l) != 0:
				r.append(l)
		return r


class Solution:

	def allPairs(self, A, B, N, M, X):
		l = []
		d = {}
		for i in A:
			d[X - i] = i
		for i in B:
			if i in d:
				l.append((d[i], i))
		return sorted(l)


class Solution:

	def allPairs(self, A, B, N, M, X):
		res = []
		A.sort()
		for i in range(N):
			if X - A[i] in B:
				res.append((A[i], X - A[i]))
		return res


class Solution:

	def allPairs(self, A, B, N, M, X):
		d = dict()
		pairs = []
		for i in range(M):
			d[B[i]] = i
		A.sort()
		for i in range(N):
			ans = X - A[i]
			if ans in d:
				pairs.append([A[i], ans])
		return pairs


class Solution:

	def allPairs(self, A, B, N, M, X):
		pairs = []
		for idx in range(N):
			if X - A[idx] in B:
				pairs.append([A[idx], X - A[idx]])
		return sorted(pairs)


class Solution:

	def allPairs(self, A, B, N, M, X):
		p = []
		for num1 in A:
			target_diff = X - num1
			for num2 in B:
				if target_diff == num2:
					p.append((num1, num2))
		p.sort()
		return p


class Solution:

	def allPairs(self, A, B, N, M, X):
		index = 0
		index2 = 0
		pairs = []
		while index < N:
			if A[index] + B[index2] == X:
				pairs.append((A[index], B[index2]))
			index2 += 1
			if index2 >= M:
				index2 = 0
				index += 1
		pairs.sort(key=lambda x: x[0])
		return pairs


class Solution:

	def allPairs(self, A, B, N, M, X):
		pair = []
		for i in A:
			target = X - i
			if target in B:
				pair.append((i, target))
				pair.sort()
		return pair


class Solution:

	def allPairs(self, A, B, N, M, X):
		pairs = []
		num_set = set(B)
		for a in A:
			target = X - a
			if target in num_set:
				pairs.append((a, target))
		pairs.sort(key=lambda pair: pair[0])
		return pairs


class Solution:

	def allPairs(self, A, B, N, M, X):
		k = 0
		a = sorted(A)
		d = {}
		for i in range(N):
			for j in range(M):
				if a[i] + B[j] == X:
					d[k] = [a[i], B[j]]
					k += 1
		return d


import math

class node:
	value = 0
	left = None
	right = None

	def __init__(self, a):
		self.value = a

class bst:
	arr = []
	root = None

	def __init__(self, b):
		self.root = node(b[0])
		self.arr = b

	def make(self):
		i = 1
		while i < len(self.arr):
			u = self.root
			w = self.root
			e = 0
			while True:
				if u == None:
					if e == 0:
						w.left = node(self.arr[i])
					else:
						w.right = node(self.arr[i])
					break
				elif u.value > self.arr[i]:
					w = u
					u = u.left
					e = 0
				else:
					w = u
					u = u.right
					e = 1
			i += 1

class Solution:

	def allPairs(self, A, B, N, M, X):
		h = []
		y = None
		y = bst(B)
		y.make()
		A.sort()
		k = 0
		while k < N:
			u = y.root
			while True:
				if u == None:
					break
				if u.value + A[k] == X:
					h.append((A[k], u.value))
					break
				elif u.value + A[k] > X:
					u = u.left
				else:
					u = u.right
			k += 1
		return h


class Solution:

	def allPairs(self, A, B, N, M, X):
		i = 0
		pair_list = []
		for i in range(N):
			for j in range(M):
				pair_sum = A[i] + B[j]
				if pair_sum == X:
					sublist = [A[i], B[j]]
					pair_list.append(sublist)
		pair_list.sort(key=lambda x: x[0])
		return pair_list


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		B.sort()
		i = 0
		j = M - 1
		res = []
		while i < N and j >= 0:
			if A[i] + B[j] == X:
				res.append((A[i], B[j]))
				i += 1
				j -= 1
			elif A[i] + B[j] < X:
				i += 1
			else:
				j -= 1
		return res


class Solution:

	def allPairs(self, A, B, N, M, X):
		outArr = []
		for b in B:
			if X - b in A:
				outArr.append([X - b, b])
		outArr.sort()
		return outArr


class Solution:

	def allPairs(self, a, b, n, m, x):
		a.sort()
		b.sort()
		ans = []
		i = 0
		j = m - 1
		while i < n and j >= 0:
			sum = a[i] + b[j]
			if sum == x:
				ans.append((a[i], b[j]))
				i += 1
			if sum < x:
				i += 1
			if sum > x:
				j -= 1
		ans.sort()
		return ans


class Solution:

	def allPairs(self, A, B, N, M, X):
		pairs = []
		setA = set(A)
		for num in B:
			complement = X - num
			if complement in setA:
				pairs.append((complement, num))
		pairs.sort()
		return pairs


from collections import defaultdict

class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		d = defaultdict(int)
		for i in range(M):
			d[B[i]] += 1
		pairs = []
		for i in range(N):
			if d[X - A[i]] > 0:
				d[X - A[i]] -= 1
				pairs.append([A[i], X - A[i]])
		return pairs


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		B.sort()
		result = []
		left = 0
		right = M - 1
		while left < N and right >= 0:
			currentSum = A[left] + B[right]
			if currentSum == X:
				result.append((A[left], B[right]))
				tempA = left
				while left < N and A[left] == A[tempA]:
					left += 1
				tempB = right
				while right >= 0 and B[right] == B[tempB]:
					right -= 1
			elif currentSum < X:
				left += 1
			else:
				right -= 1
		return result


class Solution:

	def allPairs(self, A, B, N, M, X):
		li = []
		for i in B:
			tot = X - i
			if tot in A:
				li.append((tot, i))
		li.sort()
		return li


class Solution:

	def allPairs(self, A, B, N, M, X):
		lst = list()
		for i in range(len(A)):
			for j in range(len(B)):
				if A[i] + B[j] == X:
					lst.append((A[i], B[j]))
		return sorted(lst)


class Solution:

	def allPairs(self, A, B, N, M, X):
		res = []
		A.sort()
		B.sort(reverse=True)
		for i in range(M):
			needed = X - B[i]
			left = -1
			right = N
			while right - left != 1:
				mid = (right + left) // 2
				if A[mid] < needed:
					left = mid
				elif A[mid] > needed:
					right = mid
				else:
					res.append((needed, B[i]))
					break
		return res


class Solution:

	def allPairs(self, A, B, N, M, X):
		dict2 = dict()
		result = []
		for (index, number) in enumerate(B):
			dict2[number] = index
		for number in A:
			if X - number in dict2:
				result.append([number, X - number])
		result.sort()
		return result


class Solution:

	def allPairs(self, A, B, N, M, X):
		hashB = {}
		ans = []
		for i in B:
			hashB[i] = 1 + hashB.get(i, 0)
		for i in A:
			if X - i in hashB:
				ans.append([i, X - i])
		ans.sort()
		return ans


class Solution:

	def allPairs(self, A, B, N, M, X):
		pairs = [(u, X - u) for u in A if X - u in B]
		pairs.sort()
		return pairs


class Solution:

	def allPairs(self, A, B, N, M, X):
		result = []
		hash_set = set(A)
		for i in range(M):
			complement = X - B[i]
			if complement in hash_set:
				result.append((complement, B[i]))
		result.sort(key=lambda x: x[0])
		return result


class Solution:

	def allPairs(self, A, B, N, M, X):
		d = []
		A.sort()
		B.sort()
		for i in range(0, N):
			for j in range(0, M):
				if A[i] + B[j] == X:
					d.append([A[i], B[j]])
		return d


class Solution:

	def allPairs(self, A, B, N, M, X):
		l = []
		A.sort()
		for i in A:
			for j in B:
				if i + j == X:
					l.append([i, j])
		return l


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		B.sort()
		res = []
		l = 0
		r = M - 1
		while l < N and r >= 0:
			s = A[l] + B[r]
			if s == X:
				res.append((A[l], B[r]))
				l += 1
				r -= 1
			elif s > X:
				r -= 1
			else:
				l += 1
		return res


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		l = []
		i = 0
		while i < N:
			j = 0
			while j < M:
				if A[i] + B[j] == X:
					l.append([A[i], B[j]])
				j += 1
			i += 1
		return l


class Solution:

	def allPairs(self, A, B, N, M, X):
		H = set(A)
		pairs = []
		for b in B:
			if X - b in H:
				pairs.append((X - b, b))
		pairs.sort()
		return pairs


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		B.sort()
		ans = []
		for i in range(N):
			target = X - A[i]
			l = 0
			r = M - 1
			while l <= r:
				mid = (l + r) // 2
				if B[mid] == target:
					ans.append([A[i], B[mid]])
					break
				elif B[mid] < target:
					l = mid + 1
				else:
					r = mid - 1
		return ans


class Solution:

	def allPairs(self, A, B, N, M, X):
		c = []
		for i in A:
			if X - i in B:
				c.append((i, X - i))
		c.sort(key=lambda x: x[0])
		return c


class Solution:

	def allPairs(self, A, B, N, M, X):
		d1 = {}
		d2 = {}
		result = []
		for i in range(M):
			d1[B[i]] = i
		for i in range(N):
			if X - A[i] in d1:
				result.append([A[i], X - A[i]])
		return sorted(result)


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		ans = []
		for i in range(N):
			if X - A[i] in B:
				s = [A[i], X - A[i]]
				ans.append(s)
				B.remove(X - A[i])
		return ans


class Solution:

	def allPairs(self, A, B, N, M, X):
		lst = []
		B.sort()
		A.sort()
		for i in A:
			start = 0
			end = M
			while start < end:
				mid = (start + end) // 2
				if i + B[mid] == X:
					lst.append([i, B[mid]])
					break
				elif i + B[mid] > X:
					end = mid
				else:
					start = mid + 1
		return lst


from collections import Counter

class Solution:

	def allPairs(self, A, B, N, M, X):
		lst = []
		B.sort()
		A.sort()
		dict = Counter(B)
		for i in A:
			start = 0
			end = M
			while start < end:
				mid = (start + end) // 2
				if i + B[mid] == X:
					lst.append([i, B[mid]])
					break
				elif i + B[mid] > X:
					end = mid
				else:
					start = mid + 1
		return lst


class Solution:

	def allPairs(self, A, B, N, M, X):
		k = []
		A = sorted(A)
		for i in range(len(A)):
			Y = X - A[i]
			if Y in B:
				k.append([A[i], Y])
		return k


class Solution:

	def allPairs(self, A, B, N, M, X):
		sA = A.sort()
		sB = B.sort()
		data = []
		for i in A:
			rem = X - i
			if rem in B:
				obj = [i, rem]
				data.append(obj)
		return data


class Solution:

	def allPairs(self, A, B, N, M, X):
		arr = []
		for i in range(len(A)):
			for j in range(len(B)):
				if A[i] + B[j] == X:
					arr.append([A[i], B[j]])
		if arr == []:
			return []
		arr.sort()
		return arr


from collections import Counter

class Solution:

	def allPairs(self, A, B, N, M, X):
		m = Counter(B)
		ans = []
		for i in A:
			if X - i in m:
				ans.append([i, X - i])
				m[X - i] -= 1
				if m[X - i] == 0:
					del m[X - i]
		return sorted(ans)


class Solution:

	def allPairs(self, A, B, N, M, X):
		hashmap1 = {}
		hashmap2 = {}
		res = []
		for i in range(0, N):
			hashmap1[A[i]] = i
		for i in range(0, M):
			hashmap2[B[i]] = i
		if N >= M:
			for i in range(0, N):
				diff = X - A[i]
				if diff in hashmap2:
					l = ()
					l += (A[i],)
					l += (diff,)
					res.append(l)
		if M > N:
			for i in range(0, M):
				diff = X - B[i]
				if diff in hashmap1:
					l = ()
					l += (diff,)
					l += (B[i],)
					res.append(l)
		return sorted(res)


class Solution:

	def binarySearch(self, B, M, target):
		s = 0
		e = M - 1
		ans = None
		while s <= e:
			mid = s + (e - s) // 2
			if B[mid] == target:
				ans = target
				break
			elif B[mid] > target:
				e = mid - 1
			elif B[mid] < target:
				s = mid + 1
		return ans

	def allPairs(self, A, B, N, M, X):
		ans = []
		B.sort()
		for i in range(N):
			a = A[i]
			b = self.binarySearch(B, M, X - A[i])
			if b != None:
				t = (a, b)
				ans.append(t)
		ans.sort()
		return ans


class Solution:

	def allPairs(self, A, B, N, M, X):
		b = {elem: 0 for elem in B}
		return [[elem, X - elem] for elem in sorted(A) if X - elem in b]


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		b = {elem: 0 for elem in B}
		res = []
		for elem in A:
			if X - elem in b:
				res.append([elem, X - elem])
		return res


class Solution:

	def allPairs(self, A, B, N, M, X):
		A.sort()
		B.sort()
		ans = []
		s = set()
		for i in B:
			s.add(i)
		for i in A:
			if X - i in s:
				ans.append([i, X - i])
		return ans


class Solution:

	def allPairs(self, A, B, N, M, X):
		A = sorted(A)
		res = []
		for ele in A:
			if X - ele in B:
				res.append((ele, X - ele))
		return res