Given an array of distinct integers, find all the pairs having both negative and positive values of a number in the array.
Example 1:
Input:
n = 8
arr[] = {1,3,6,-2,-1,-3,2,7}
Output: -1 1 -3 3 -2 2
Explanation: 1, 3 and 2 are present 
pairwise positive and negative. 6 and 
7 have no pair.
Example 2:
Input:
n = 3
arr[] = {3,2,1}
Output: 0
Explanation: No such pair exists so the 
output is 0.
Your Task:
You do not need to read input or print anything. Complete the function findPairs() which takes the array A[] and the size of the array, n, as input parameters and returns a list of integers denoting the pairs. The pair that appears first(i.e. second element of the pair appears first) in A[] should appear first in the returning list and within the pair, the negative integer should appear before the positive integer. Return an empty integer list if no such pair exists. 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 <= n <= 10^{6}
-10^{6} <= arr[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    #Function to return list containing all the pairs having both

    #negative and positive values of a number in the array.

    def findPairs(self,arr,n):

        # code here 

Solutions:
class Solution:

	def findPairs(self, arr, n):
		x = set()
		li = []
		for i in arr:
			x.add(i)
			if -1 * i in x and i != 0:
				if i > 0:
					li.append(-1 * i)
					li.append(i)
				else:
					li.append(i)
					li.append(-1 * i)
		return li


class Solution:

	def findPairs(self, arr, n):
		l = []
		dict = {}
		for i in arr:
			if -i in dict:
				if i < 0:
					l.extend([i, i * -1])
				else:
					l.extend([i * -1, i])
			else:
				dict[i] = 'h'
		return l


from collections import *

class Solution:

	def findPairs(self, arr, n):
		hashset = set()
		ans = []
		for i in range(n):
			if -arr[i] in hashset:
				if arr[i] < 0:
					ans.append(arr[i])
					ans.append(-arr[i])
				else:
					ans.append(-arr[i])
					ans.append(arr[i])
			hashset.add(arr[i])
		return ans


class Solution:

	def findPairs(self, arr, n):
		hash = set()
		res = []
		for el in arr:
			if -el in hash:
				res += sorted([el, -el])
			hash.add(el)
		return res


class Solution:

	def findPairs(self, arr, n):
		l1 = {}
		ans = []
		for i in arr:
			if i * -1 in l1:
				num = abs(i)
				ans.append(num * -1)
				ans.append(num)
			else:
				l1[i] = i
		return ans


class Solution:

	def findPairs(self, arr, n):
		ans = []
		s = set()
		for i in arr:
			s.add(i)
			if -i in s and i != 0:
				ans.append(min(i, -i))
				ans.append(max(i, -i))
		if len(ans) == 0:
			return [0]
		return ans


class Solution:

	def findPairs(self, arr, n):
		dic = {}
		d = []
		count = 1
		for i in range(n):
			if abs(arr[i]) in dic:
				d.append(-abs(arr[i]))
				d.append(abs(arr[i]))
			else:
				dic[abs(arr[i])] = 1
		return d


class Solution:

	def findPairs(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = [i]
			else:
				d[arr[i]].append(i)
		l = []
		for i in arr:
			if i > 0:
				l.append(i)
		d2 = []
		for i in l:
			try:
				if d[i] > d[-i]:
					d2.append([d[i][0], -i, i])
				else:
					d2.append([d[-i][0], -i, i])
			except:
				pass
		l2 = []
		d2.sort()
		for i in d2:
			l2.append(i[1])
			l2.append(i[2])
		return l2


class Solution:

	def findPairs(self, arr, n):
		res = []
		s = set()
		for i in arr:
			if -i in s:
				res.append(-abs(i))
				res.append(abs(i))
			s.add(i)
		return res


class Solution:

	def findPairs(self, arr, n):
		pairWiseArr = []
		sets = set()
		for ele in arr:
			if -1 * ele not in sets:
				sets.add(ele)
			else:
				pairWiseArr.append(min(ele, -1 * ele))
				pairWiseArr.append(max(ele, -1 * ele))
		return pairWiseArr


class Solution:

	def findPairs(self, arr, n):
		table = {}
		A = []
		for i in arr:
			if i >= 0:
				if -i in table:
					A.append(-i)
					A.append(i)
				else:
					table[i] = 1
			if i < 0:
				if -i in table:
					A.append(i)
					A.append(-i)
				else:
					table[i] = 1
		return A


class Solution:

	def findPairs(self, arr, n):
		if n == 1:
			return []
		hset = set()
		res = []
		for val in arr:
			if val == 0:
				continue
			if -val in hset:
				res.append(-1 * abs(val))
				res.append(abs(val))
			hset.add(val)
		return res


class Solution:

	def findPairs(self, arr, n):
		d = dict()
		l = []
		for i in arr:
			if i * -1 in d.keys():
				if i < 0:
					l.append(i)
					l.append(i * -1)
				else:
					l.append(i * -1)
					l.append(i)
			else:
				d[i] = i
		return l


class Solution:

	def findPairs(self, arr, n):
		s = {}
		x = []
		res = []
		for i in range(n):
			a = arr[i]
			s[a] = i
			if a > 0 and -1 * a in s or (a < 0 and -1 * a in s):
				indexOfFirstPair = s[-1 * a]
				res.append(-1 * abs(arr[indexOfFirstPair]))
				res.append(abs(arr[indexOfFirstPair]))
		return res


class Solution:

	def findPairs(self, arr, n):
		if n == 0:
			return [0]
		d = {}
		ans = []
		d[arr[0]] = 0
		for i in range(1, n):
			if -1 * arr[i] in d:
				temp = arr[i]
				temp1 = -1 * arr[i]
				if temp > temp1:
					ans.append(temp1)
					ans.append(temp)
				else:
					ans.append(temp)
					ans.append(temp1)
			d[arr[i]] = i
		return ans


class Solution:

	def findPairs(self, arr, n):
		a = set()
		b = []
		ans = []
		for i in arr:
			if -1 * i not in a:
				a.add(i)
			else:
				ans += [-1 * abs(i), abs(i)]
		return ans


class Solution:

	def findPairs(self, arr, n):
		hashSet = set()
		ans = []
		for i in range(n):
			if -arr[i] in hashSet:
				if arr[i] < 0:
					ans.append(arr[i])
					ans.append(-arr[i])
				else:
					ans.append(-arr[i])
					ans.append(arr[i])
			hashSet.add(arr[i])
		return ans


class Solution:

	def findPairs(self, arr, n):
		hashSet = set()
		ans = []
		for num in arr:
			hashSet.add(num)
			if -num in hashSet and num != 0:
				ans.append(-abs(num))
				ans.append(abs(num))
				hashSet.remove(num)
				hashSet.remove(-num)
		return ans


class Solution:

	def findPairs(self, arr, n):
		s = set()
		lt = []
		for a in arr:
			c = a * -1
			if c in s:
				if c < 0:
					lt.append(c)
					lt.append(a)
				else:
					lt.append(a)
					lt.append(c)
			else:
				s.add(a)
		return lt


class Solution:

	def findPairs(self, arr, n):
		s = set()
		res = []
		for item in arr:
			if -1 * item in s:
				res.extend([-abs(item), abs(item)])
				s.remove(-1 * item)
			else:
				s.add(item)
		return res


class Solution:

	def findPairs(self, arr, n):
		s = set()
		res = []
		for i in range(n):
			if arr[i] * -1 in s:
				if arr[i] > 0:
					res.append(arr[i] * -1)
					res.append(arr[i])
				else:
					res.append(arr[i])
					res.append(arr[i] * -1)
			s.add(arr[i])
		return res


class Solution:

	def findPairs(self, arr, n):
		d = {}
		l = []
		for i in arr:
			if i in d or i * -1 in d:
				r = abs(i)
				l.append(r * -1)
				l.append(r)
			else:
				d[i] = 1
		return l


class Solution:

	def findPairs(self, arr, n):
		resList = []
		mdict = {}
		for num in arr:
			if num in mdict or num * -1 in mdict:
				n1 = abs(num)
				resList.append(n1 * -1)
				resList.append(n1)
			mdict[num] = num
		return resList


class Solution:

	def findPairs(self, arr, n):
		List = []
		hash_map = dict()
		for i in arr:
			if i not in hash_map:
				hash_map[i] = 1
			else:
				hash_map[i] += 1
		for i in range(n - 1, -1, -1):
			if arr[i] != 0:
				if -arr[i] in hash_map:
					if arr[i] < 0:
						List.append(-arr[i])
						List.append(arr[i])
					else:
						List.append(arr[i])
						List.append(-arr[i])
					if arr[i] in hash_map:
						del hash_map[arr[i]]
						if i != 0:
							del hash_map[-arr[i]]
		List.reverse()
		return List


class Solution:

	def findPairs(self, arr, n):
		res = []
		s = set()
		for x in arr:
			if -x in s:
				res.extend([-x, x] if x > 0 else [x, -x])
			else:
				s.add(x)
		return res


class Solution:

	def findPairs(self, arr, n):
		h = set()
		res = []
		for i in arr:
			if -i in h:
				if i < 0:
					res.append(i)
					res.append(-i)
				else:
					res.append(-i)
					res.append(i)
			h.add(i)
		return res


from collections import OrderedDict
import math

class Solution:

	def findPairs(self, arr, n):
		list1 = []
		d = OrderedDict()
		for i in arr:
			d[i] = 1
			if -i in d:
				if i != 0:
					list1.append(-1 * abs(i))
					list1.append(abs(i))
		return list1


class Solution:

	def findPairs(self, arr, n):
		if n == 0:
			return []
		mx = max(max(arr), -min(arr))
		l = [0] * (mx + 1)
		res = []
		for i in arr:
			if i > 0:
				l[i] += 1
				if l[i] == 2:
					res.append(-i)
					res.append(i)
			else:
				l[-i] += 1
				if l[-i] == 2:
					res.append(i)
					res.append(-i)
		return res


class Solution:

	def findPairs(self, arr, n):
		d = {}
		B = []
		for i in range(n):
			data = abs(arr[i])
			if data in d:
				B.append(-1 * data)
				B.append(data)
			else:
				d[data] = 1
		return B


class Solution:

	def findPairs(self, arr, n):
		d = {}
		lst = []
		for i in range(n):
			if abs(arr[i]) in d:
				self.fn(lst, abs(arr[i]))
			else:
				d[abs(arr[i])] = 1
		return lst

	def fn(self, lst, x):
		lst.append(-x)
		lst.append(x)
		return lst


class Solution:

	def findPairs(self, arr, n):
		from collections import OrderedDict
		sol = []
		dict1 = OrderedDict({})
		for i in range(len(arr)):
			if arr[i] > 0:
				dict1[arr[i]] = dict1.get(arr[i], True)
				if dict1.get(0 - arr[i]) and arr[i] != 0:
					sol.append(0 - arr[i])
					sol.append(arr[i])
			else:
				dict1[arr[i]] = dict1.get(arr[i], True)
				if dict1.get(0 - arr[i]) and arr[i] != 0:
					sol.append(arr[i])
					sol.append(0 - arr[i])
		return sol


from collections import OrderedDict

class Solution:

	def findPairs(self, arr, n):
		o = OrderedDict()
		result = []
		for item in arr:
			if -item in o:
				result.append(min(item, -item))
				result.append(max(item, -item))
			o[item] = 1
		return result


class Solution:

	def findPairs(self, arr, n):
		d = dict()
		pair = []
		for a in arr:
			a = abs(a)
			d[a] = d.get(a, 0) + 1
			if d[a] == 2:
				pair.extend([-a, a])
		return pair


class Solution:

	def findPairs(self, arr, n):
		integer = dict()
		a = []
		for i in range(n):
			if integer.get(-arr[i], 0) != 0:
				a.append(min(arr[i], -arr[i]))
				a.append(max(arr[i], -arr[i]))
				del integer[-arr[i]]
			else:
				integer[arr[i]] = 1
		return a


class Solution:

	def findPairs(self, arr, n):
		pairs = []
		s = set()
		for num in arr:
			if -num in s:
				pairs.append(min(num, -num))
				pairs.append(max(num, -num))
			else:
				s.add(num)
		return pairs


class Solution:

	def findPairs(self, arr, n):
		pair_dict = {}
		output = []
		for element in arr:
			if element == 0:
				continue
			pair_dict[element] = True
			if pair_dict.get(-element, False):
				if element < 0:
					output.append(element)
					output.append(-element)
				else:
					output.append(-element)
					output.append(element)
		return output


class Solution:

	def findPairs(self, arr, n):
		dt = {}
		result = []
		for i in range(n):
			if abs(arr[i]) in dt:
				if arr[i] < 0:
					result.append(arr[i])
					result.append(dt[abs(arr[i])])
				else:
					result.append(dt[abs(arr[i])])
					result.append(arr[i])
			else:
				dt[abs(arr[i])] = arr[i]
		return result


from collections import defaultdict

class Solution:

	def findPairs(self, arr, n):
		mp = defaultdict(lambda : None)
		ans = []
		for i in range(n):
			if -arr[i] in mp:
				if -arr[i] < 0:
					ans.append(-arr[i])
					ans.append(arr[i])
				else:
					ans.append(arr[i])
					ans.append(-arr[i])
			mp[arr[i]] = i
		return ans


class Solution:

	def findPairs(self, arr, n):
		dic = {}
		res = []
		for i in arr:
			if -i in dic:
				if i < 0:
					res.append([i, -i])
				else:
					res.append([-i, i])
			else:
				dic[i] = 1
		res1 = []
		for (i, v) in res:
			res1.append(i)
			res1.append(v)
		return res1


class Solution:

	def findPairs(self, arr, n):
		s = {}
		res = []
		for i in range(n):
			if -arr[i] in s and s[-arr[i]] > 0:
				res.append(-1 * abs(arr[i]))
				res.append(abs(arr[i]))
				s[-arr[i]] -= 1
			elif arr[i] in s:
				s[arr[i]] += 1
			else:
				s[arr[i]] = 1
		return res


class Solution:

	def findPairs(self, arr, n):
		lookup = set()
		res = []
		for elem in arr:
			if -1 * elem in lookup:
				res.append(-1 * abs(elem))
				res.append(abs(elem))
			lookup.add(elem)
		return res


class Solution:

	def findPairs(self, arr, n):
		d = set()
		c = []
		for i in range(n):
			if arr[i] * -1 in d:
				if arr[i] < 0:
					c.append(arr[i])
					c.append(-arr[i])
				else:
					c.append(-arr[i])
					c.append(arr[i])
			d.add(arr[i])
		return c


from collections import defaultdict

class Solution:

	def findPairs(self, arr, n):
		complement = defaultdict(int)
		result = []
		for i in range(n):
			if -arr[i] in complement:
				if arr[i] < 0:
					result.append(arr[i])
					result.append(-arr[i])
				else:
					result.append(-arr[i])
					result.append(arr[i])
			else:
				complement[arr[i]]
		return result


class Solution:

	def findPairs(self, arr, n):
		l = []
		d = {}
		for ele in arr:
			z = abs(ele)
			if z in d.keys():
				d[z] = d.get(z) + ele
				if d.get(z) == 0:
					l.append(-z)
					l.append(z)
			else:
				d[z] = ele
		return l


class Solution:

	def findPairs(self, arr, n):
		a = []
		d = {}
		for i in arr:
			if i in d or i * -1 in d:
				n1 = abs(i)
				a.append(n1 * -1)
				a.append(n1)
			d[i] = i
		return a


class Solution:

	def findPairs(self, arr, n):
		x = []
		hs = set()
		for i in range(n):
			if arr[i] * -1 in hs:
				x.append(-1 * abs(arr[i]))
				x.append(abs(arr[i]))
			hs.add(arr[i])
		return x


class Solution:

	def findPairs(self, arr, n):
		items = set([])
		response = []
		for i in arr:
			if i * -1 in items:
				response.append(-abs(i))
				response.append(abs(i))
			items.add(i)
		return response


class Solution:

	def findPairs(self, arr, n):
		arr1 = set(arr)
		res = []
		d = {}
		for i in arr:
			if i not in d.keys():
				if i * -1 in arr1:
					d[i * -1] = 1
			elif d[i] >= 1:
				if i < 0:
					res.append(i)
					res.append(i * -1)
				else:
					res.append(i * -1)
					res.append(i)
		return res


class Solution:

	def findPairs(self, a, n):
		d = {}
		l = []
		for i in a:
			if i not in d:
				d[-1 * i] = 1
			else:
				m = [i, -1 * i]
				l.append(min(m))
				l.append(max(m))
		return l


class Solution:

	def findPairs(self, arr, n):
		pair = {}
		li = []
		for a in arr:
			pair[a] = 0
			if a != 0 and -a in pair.keys():
				if a < 0:
					li.append(a)
					li.append(-a)
				else:
					li.append(-a)
					li.append(a)
				del pair[a]
				if a != 0:
					del pair[-a]
		return li


class Solution:

	def findPairs(self, array, n):
		hashset = set()
		result = []
		for i in range(n):
			if array[i] * -1 in hashset:
				if array[i] < 0:
					result.extend([array[i], array[i] * -1])
				else:
					result.extend([array[i] * -1, array[i]])
			hashset.add(array[i])
		return result


class Solution:

	def findPairs(self, arr, n):
		hf = set()
		ans = []
		for i in range(n):
			if arr[i] * -1 in hf:
				ans.append(str(-abs(arr[i])))
				ans.append(str(abs(arr[i])))
			else:
				hf.add(arr[i])
		return ans


class Solution:

	def findPairs(self, arr, n):
		se = set()
		re = list()
		for i in arr:
			if abs(i) not in se:
				se.add(abs(i))
			else:
				re.append(-abs(i))
				re.append(abs(i))
				se.remove(abs(i))
		return re


class Solution:

	def findPairs(self, arr, n):
		r = []
		d = {}
		for i in range(n):
			arr[i] = abs(arr[i])
		for i in arr:
			if i not in d:
				d[i] = 1
			elif i in d:
				d[i] += 1
				if d[i] == 2:
					r.append(-i)
					r.append(i)
					del d[i]
		return r


class Solution:

	def findPairs(self, arr, n):
		from collections import defaultdict
		d = defaultdict(int)
		res = []
		for i in arr:
			if d[-i] == 1:
				res.append(-abs(i))
				res.append(abs(i))
				d[-i] = 0
			elif d[-i] == 0:
				d[i] = 1
		return res


class Solution:

	def findPairs(self, arr, n):
		d = {}
		res = []
		for i in arr:
			if -i in d.keys():
				res.append(-abs(i))
				res.append(abs(i))
			else:
				d[i] = 0
		return res


class Solution:

	def findPairs(self, arr, n):
		s = set()
		res = []
		for i in arr:
			if -i in s:
				pos = max(i, -i)
				neg = min(i, -i)
				res.append(neg)
				res.append(pos)
			s.add(i)
		return res


class Solution:

	def findPairs(self, arr, n):
		l = []
		p = {}
		neg = {}
		for i in arr:
			if -i in p:
				a = min(-i, i)
				b = max(i, -i)
				l.append(a)
				l.append(b)
			else:
				p[i] = 1
		return l


class Solution:

	def findPairs(self, arr, n):
		ans = []
		d = {}
		for i in arr:
			if i in d or -i in d:
				temp = abs(i)
				ans += [-temp, temp]
			d[i] = i
		return ans


class Solution:

	def findPairs(self, arr, n):
		if n == 0:
			return []
		m = max(arr)
		m1 = min(arr) - 1
		if m > abs(m1):
			hashm = [10 ** 6 + 1] * (m + 1)
		else:
			hashm = [10 ** 6 + 1] * (abs(m1) + 1)
		res = []
		for i in range(n):
			if hashm[abs(arr[i])] != 10 ** 6 + 1:
				if arr[i] < 0:
					res.append(arr[i])
					res.append(hashm[abs(arr[i])])
				else:
					res.append(hashm[abs(arr[i])])
					res.append(arr[i])
			else:
				hashm[abs(arr[i])] = arr[i]
		return res


class Solution:

	def findPairs(self, arr, n):
		ans = []
		Hash = {}
		for i in range(n):
			k = arr[i]
			if -1 * k in Hash:
				if k > 0:
					ans.append(-k)
				else:
					ans.append(k)
				ans.append(abs(k))
			else:
				Hash[k] = 1
		if len(ans) == 0:
			return [0]
		return ans


class Solution:

	def findPairs(self, arr, n):
		s = set()
		res = []
		for e in arr:
			if abs(e) not in s:
				s.add(abs(e))
			else:
				res.extend([-abs(e), abs(e)])
		return res


class Solution:

	def findPairs(self, arr, n):
		table = {}
		ans = []
		for i in range(n):
			num = abs(arr[i])
			if num not in table:
				table[num] = 1
			else:
				ans.extend([-num, num])
		return ans


class Solution:

	def findPairs(self, arr, n):
		ans = []
		dict = {}
		for i in arr:
			if i in dict or i * -1 in dict:
				j = abs(i)
				ans.append(j * -1)
				ans.append(j)
			dict[i] = i
		return ans


class Solution:

	def findPairs(self, arr, n):
		hash = set()
		res = []
		for a in arr:
			e = abs(a)
			if e in hash:
				res.append(-e)
				res.append(e)
			else:
				hash.add(e)
		return res


class Solution:

	def findPairs(self, arr, n):
		ans = []
		dic = {}
		for num in arr:
			if num in dic or num * -1 in dic:
				n1 = abs(num)
				ans.append(n1 * -1)
				ans.append(n1)
			dic[num] = num
		if len(ans) == 0:
			ans.append(0)
		return ans


class Solution:

	def findPairs(self, arr, n):
		helper = set()
		res = []
		for i in range(n):
			if -arr[i] in helper:
				res.append(-1 * abs(arr[i]))
				res.append(abs(arr[i]))
			helper.add(arr[i])
		return res


class Solution:

	def findPairs(self, arr, n):
		d = {}
		res = []
		for i in range(n):
			if -1 * arr[i] in d:
				res.append(min(arr[i], -1 * arr[i]))
				res.append(max(arr[i], -1 * arr[i]))
				d[-1 * arr[i]] -= 1
			elif arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		return res


class Solution:

	def findPairs(self, arr, n):
		st = set()
		list = []
		for i in arr:
			if abs(i) in st:
				list.append(-abs(i))
				list.append(abs(i))
			else:
				st.add(abs(i))
		return list


class Solution:

	def findPairs(self, arr, n):
		hashh = set()
		res = []
		for i in arr:
			if -1 * i in hashh:
				res.append(-1 * abs(i))
				res.append(abs(i))
			else:
				hashh.add(i)
		return res


class Solution:

	def findPairs(self, arr, n):
		ans = []
		s = set()
		for i in arr:
			if -i in s:
				if i < 0:
					ans.append(i)
					ans.append(-i)
				else:
					ans.append(-i)
					ans.append(i)
			s.add(i)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		res = Solution().findPairs(arr, n)
		if len(res) == 0:
			print(0)
		else:
			for x in res:
				print(x, end=' ')
			print()


class Solution:

	def findPairs(self, arr, n):
		di = {}
		li = []
		for i in arr:
			if i * -1 in di:
				if i < 0:
					li.append(i)
					li.append(-1 * i)
				else:
					li.append(-1 * i)
					li.append(i)
			di[i] = 1
		return li
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		res = Solution().findPairs(arr, n)
		if len(res) == 0:
			print(0)
		else:
			for x in res:
				print(x, end=' ')
			print()