Given a set of N nuts of different sizes and N bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.
Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.
The elements should follow the following order ! # $ % & * @ ^ ~ .
Example 1:
Input: 
N = 5
nuts[] = {@, %, $, #, ^}
bolts[] = {%, @, #, $ ^}
Output: 
# $ % @ ^
# $ % @ ^
Example 2:
Input: 
N = 9
nuts[] = {^, &, %, @, #, *, $, ~, !}
bolts[] = {~, #, @, %, &, *, $ ,^, !}
Output: 
! # $ % & * @ ^ ~
! # $ % & * @ ^ ~
Your Task:  
You don't need to read input or print anything. Your task is to complete the function matchPairs() which takes an array of characters nuts[], bolts[] and n as parameters and returns void. You need to change the array itself.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 9
Array of Nuts/Bolts can only consist of the following elements:{'@', '#', '$', '%', '^', '&', '~', '*', '!'}.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3
class Solution:

	def matchPairs(self,nuts, bolts, n):
		# code here

Solutions:
class Solution:

	def matchPairs(self, nuts, bolts, n):
		ord = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		matcher = dict()
		for i in nuts:
			matcher[i] = 1
		for j in bolts:
			matcher[j] += 1
		res = []
		for o in ord:
			if matcher.get(o) == 2:
				res.append(o)
		nuts.clear()
		nuts.extend(res)
		bolts.clear()
		bolts.extend(res)


class Solution:

	def matchPairs(self, nuts, bolts, n):

		def partition(arr, low: int, high: int, pivot: str) -> int:
			i = low
			j = low
			while j < high:
				if arr[j] < pivot:
					(arr[i], arr[j]) = (arr[j], arr[i])
					i += 1
				elif arr[j] == pivot:
					(arr[j], arr[high]) = (arr[high], arr[j])
					j -= 1
				j += 1
			(arr[i], arr[high]) = (arr[high], arr[i])
			return i

		def mP(nuts, bolts, low: int, high: int) -> None:
			if low < high:
				pivot = partition(nuts, low, high, bolts[high])
				partition(bolts, low, high, nuts[pivot])
				mP(nuts, bolts, low, pivot - 1)
				mP(nuts, bolts, pivot + 1, high)
		mP(nuts, bolts, 0, n - 1)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		d = {'!': 1, '#': 2, '$': 3, '%': 4, '&': 5, '*': 6, '@': 7, '^': 8, '~': 9}
		x = [[] for i in range(1, 10)]
		for i in nuts:
			x[d[i] - 1].append(i)
		result1 = []
		for i in x:
			if len(i) > 0:
				result1.extend(i)
		for i in range(len(result1)):
			nuts[i] = result1[i]
		for i in range(len(nuts)):
			bolts[i] = nuts[i]


class Solution:

	def matchPairs(self, nuts, bolts, n):
		dic = {'!': 1, '#': 2, '$': 3, '%': 4, '&': 5, '*': 6, '@': 7, '^': 8, '~': 9}
		nuts = nuts.sort(key=lambda x: dic[x])
		bolts = bolts.sort(key=lambda x: dic[x])


class Solution:

	def matchPairs(self, nuts, bolts, n):
		s = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		d = 0
		for i in s:
			if i in nuts:
				nuts.remove(i)
				bolts.remove(i)
				nuts.insert(d, i)
				bolts.insert(d, i)
				d += 1


class Solution:

	def matchPairs(self, nuts, bolts, n):
		nuts.sort()
		bolts.sort()


class Solution:

	def matchPairs(self, nuts, bolts, n):
		l = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		nut = nuts[:]
		bolt = bolts[:]
		i = 0
		for c in l:
			if nut.__contains__(c) and bolt.__contains__(c):
				nuts[i] = c
				bolts[i] = c
				i += 1


class Solution:

	def get_partition(self, arr, start, end, p_value):
		i = start
		j = start
		while j < end:
			if arr[j] < p_value:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
			elif arr[j] == p_value:
				(arr[end], arr[j]) = (arr[j], arr[end])
				j -= 1
			j += 1
		(arr[end], arr[i]) = (arr[i], arr[end])
		return i

	def match_pair(self, nuts, bolts, start, end):
		if start < end:
			p = self.get_partition(nuts, start, end, bolts[end])
			self.get_partition(bolts, start, end, nuts[p])
			self.match_pair(nuts, bolts, start, p - 1)
			self.match_pair(nuts, bolts, p + 1, end)

	def matchPairs(self, nuts, bolts, n):
		self.match_pair(nuts, bolts, 0, n - 1)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		s = '!#$%&*@^~'
		f = {}
		for i in nuts:
			f[i] = f.get(i, 0) + 1
		j = 0
		for i in s:
			for k in range(f.get(i, 0)):
				nuts[j] = i
				bolts[j] = i
				j += 1


class Solution:

	def matchPairs(self, nuts, bolts, n):
		order = {'!': 0, '#': 1, '$': 2, '%': 3, '&': 4, '*': 5, '@': 6, '^': 7, '~': 8}
		nuts.sort(key=lambda x: order[x])
		bolts.sort(key=lambda x: order[x])
		return (nuts, bolts)


class Solution:

	def __init__(self):
		pass

	def priority(self, x):
		if x == '!':
			return 1
		if x == '#':
			return 2
		if x == '$':
			return 3
		if x == '%':
			return 4
		if x == '&':
			return 5
		if x == '*':
			return 6
		if x == '@':
			return 7
		if x == '^':
			return 8
		if x == '~':
			return 9

	@staticmethod
	def cmp(a, b):
		sol = Solution()
		return sol.priority(a) < sol.priority(b)

	def matchPairs(self, nuts, bolts, n):
		nuts.sort(key=lambda x: self.priority(x))
		bolts.sort(key=lambda x: self.priority(x))


class Solution:

	def matchPairs(self, nuts, bolts, n):
		l = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		p = 0
		x = []
		for i in range(len(l)):
			if l[p] in nuts and l[p] in bolts:
				x.append(l[p])
			p = p + 1
		for i in range(len(nuts)):
			nuts[i] = x[i]
			bolts[i] = x[i]


class Solution:

	def matchPairs(self, nuts, bolts, n):
		ref = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		ans = []
		for val in ref:
			if val in nuts:
				ans.append(val)
		for i in range(len(nuts)):
			nuts.pop()
		for val in ans:
			nuts.append(val)
		for i in range(len(bolts)):
			bolts.pop()
		for val in ans:
			bolts.append(val)


from collections import Counter

class Solution:

	def matchPairs(self, nuts, bolts, n):
		c1 = Counter(nuts)
		c2 = Counter(bolts)
		s = '!#$%&*@^~'
		ans = []
		for i in s:
			if c1[i] > 0 and c2[i] > 0:
				ans.extend(min(c1[i], c2[i]) * [i])
		nuts[:] = ans
		bolts[:] = ans


class Solution:

	def matchPairs(self, nuts, bolts, n):
		res = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		ans = [0] * len(res)
		for i in nuts:
			ans[res.index(i)] = 1
		ind = 0
		for i in range(len(ans)):
			if ans[i]:
				nuts[ind] = res[i]
				bolts[ind] = res[i]
				ind += 1


class Solution:

	def matchPairs(self, nuts, bolts, n):
		s = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		for i in s:
			if i in nuts:
				nuts.append(i)
				nuts.remove(i)
				bolts.append(i)
				bolts.remove(i)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		arr = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		ans1 = []
		for i in arr:
			if i in nuts:
				ans1.append(i)
		for i in range(len(nuts)):
			nuts[i] = ans1[i]
			bolts[i] = ans1[i]


class Solution:

	def matchPairs(self, nuts, bolts, n):
		nuts.sort()
		for i in range(len(nuts)):
			if nuts[i] in bolts:
				t = bolts.index(nuts[i])
			if i == t:
				continue
			else:
				temp = bolts[i]
				bolts[i] = bolts[t]
				bolts[t] = temp


from functools import cmp_to_key

class Solution:

	def matchPairs(self, nuts, bolts, n):
		nuts.sort()
		bolts.sort()


class Solution:

	def get_key(self, val, my_dict):
		for (key, value) in my_dict.items():
			if val == value:
				return key

	def matchPairs(self, nuts, bolts, n):
		ele_order = {'!': 0, '#': 1, '$': 2, '%': 3, '&': 4, '*': 5, '@': 6, '^': 7, '~': 8}
		for i in range(n):
			nuts[i] = ele_order[nuts[i]]
			bolts[i] = ele_order[bolts[i]]
		nuts.sort()
		bolts.sort()
		for i in range(n):
			if nuts[i] == bolts[i]:
				nuts[i] = bolts[i] = self.get_key(nuts[i], ele_order)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		for i in range(n):
			for j in range(i, n):
				if nuts[i] > nuts[j]:
					(nuts[i], nuts[j]) = (nuts[j], nuts[i])
		for i in range(n):
			for j in range(i, n):
				if bolts[i] > bolts[j]:
					(bolts[i], bolts[j]) = (bolts[j], bolts[i])


class Solution:

	def matchPairs(self, nuts, bolts, n):
		d = {'!': 0, '#': 1, '$': 2, '%': 3, '&': 4, '*': 5, '@': 6, '^': 7, '~': 8}
		d_ = {0: '!', 1: '#', 2: '$', 3: '%', 4: '&', 5: '*', 6: '@', 7: '^', 8: '~'}
		for i in range(n):
			nuts[i] = d[nuts[i]]
		for i in range(n):
			bolts[i] = d[bolts[i]]
		nuts.sort()
		bolts.sort()
		for i in range(n):
			nuts[i] = d_[nuts[i]]
		for i in range(n):
			bolts[i] = d_[bolts[i]]


class Solution:

	def matchPairs(self, nuts, bolts, n):
		d = {'!': 1, '#': 2, '$': 3, '%': 4, '&': 5, '*': 6, '@': 7, '^': 8, '~': 9}
		for i in range(len(nuts) - 1):
			for j in range(len(nuts) - 1 - i):
				if nuts[j] > nuts[j + 1]:
					(nuts[j], nuts[j + 1]) = (nuts[j + 1], nuts[j])
		for i in range(len(bolts) - 1):
			for j in range(len(bolts) - 1 - i):
				if bolts[j] > bolts[j + 1]:
					(bolts[j], bolts[j + 1]) = (bolts[j + 1], bolts[j])


class Solution:

	def matchPairs(self, nuts, bolts, n):
		st = '!#$%&*@^~'
		d = {st[x]: x for x in range(len(st))}
		nuts.sort(key=lambda s: d[s])
		bolts.sort(key=lambda s: d[s])


class Solution:

	def matchPairs(self, nuts, bolts, n):
		stg = '!#$%&*@^~'
		dic = {}
		for i in range(len(stg)):
			dic[stg[i]] = i
		nuts.sort(key=lambda x: dic[x])
		bolts.sort(key=lambda x: dic[x])


class Solution:

	def matchPairs(self, nuts, bolts, n):
		nuts.sort()
		bolts.sort()
		(i, j) = (0, 0)
		list1 = []
		(k, l) = (0, 0)
		while i < n and j < n:
			if nuts[i] == bolts[j]:
				nuts[k] = nuts[i]
				k += 1
				bolts[l] = bolts[j]
				l += 1
				i += 1
				j += 1
			elif nuts[i] > bolts[j]:
				j += 1
			elif nuts[i] < bolts[j]:
				i += 1
		return (nuts, bolts)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		return self.matchPairsUtil(nuts, bolts, 0, n - 1)

	def matchPairsUtil(self, nuts, bolts, start, end):
		if start < end:
			pivot = self.partetion(nuts, start, end, bolts[end])
			self.partetion(bolts, start, end, nuts[pivot])
			self.matchPairsUtil(nuts, bolts, start, pivot - 1)
			self.matchPairsUtil(nuts, bolts, pivot + 1, end)

	def partetion(self, arr, start, end, pivot):
		i = start
		j = start
		while j < end:
			if arr[j] < pivot:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
			if arr[j] == pivot:
				(arr[j], arr[end]) = (arr[end], arr[j])
				j -= 1
			j += 1
		(arr[i], arr[end]) = (arr[end], arr[i])
		return i


import collections

class Solution:

	def matchPairs(self, nuts, bolts, n):
		mp = collections.Counter(nuts)
		d = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		y = 0
		for i in range(9):
			if mp[d[i]]:
				nuts[y] = d[i]
				bolts[y] = d[i]
				y += 1


class Solution:

	def matchPairs(self, nuts, bolts, n):
		nuts.sort()
		bolts.sort()
		ans = []
		for i in range(n):
			ans.append([nuts[i], bolts[i]])
		return ans


class Solution:

	def matchPairs(self, nuts, bolts, n):
		a = nuts.sort()
		b = bolts.sort()
		return a
		return b


class Solution:

	def matchPairs(self, nuts, bolts, n):
		d = {'!': 0, '#': 1, '$': 2, '%': 3, '&': 4, '*': 5, '@': 6, '^': 7, '~': 8, '.': 9}
		d1 = {0: '!', 1: '#', 2: '$', 3: '%', 4: '&', 5: '*', 6: '@', 7: '^', 8: '~', 9: '.'}
		nuts1 = []
		bolts1 = []
		for ele in nuts:
			nuts1.append(d[ele])
		for ele in bolts:
			bolts1.append(d[ele])
		nuts1 = sorted(nuts1)
		bolts1 = sorted(bolts1)
		while len(nuts) > 0:
			nuts.remove(nuts[-1])
		while len(bolts) > 0:
			bolts.remove(bolts[-1])
		for ele in nuts1:
			nuts.append(d1[ele])
		for ele in bolts1:
			bolts.append(d1[ele])


class Solution:
	mapping = {'!': 1, '#': 2, '$': 3, '%': 4, '&': 5, '*': 6, '@': 7, '^': 8, '~': 9}

	def merge_arr(self, low, mid, high, arr):
		l = low
		h = mid + 1
		k = 0
		ans = list()
		while l <= mid and h <= high:
			if self.mapping[arr[l]] < self.mapping[arr[h]]:
				ans.append(arr[l])
				l += 1
			else:
				ans.append(arr[h])
				h += 1
		while l <= mid:
			ans.append(arr[l])
			l += 1
		while h <= high:
			ans.append(arr[h])
			h += 1
		for i in range(low, high + 1):
			arr[i] = ans.pop(0)

	def merge_sort(self, low, high, arr):
		if low < high:
			mid = (high + low) // 2
			self.merge_sort(low, mid, arr)
			self.merge_sort(mid + 1, high, arr)
			self.merge_arr(low, mid, high, arr)

	def matchPairs(self, nuts, bolts, n):
		self.merge_sort(0, n - 1, nuts)
		self.merge_sort(0, n - 1, bolts)


class Solution:

	def matchPairs(self, p_nuts, p_bolts, n):
		import random
		global nuts
		global bolts
		lst = []
		x = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		for i in x:
			if i in p_nuts:
				lst += [i]
		nuts = lst
		bolts = lst


class Solution:

	def matchPairs(self, p_nuts, p_bolts, n):
		import random
		global nuts
		global bolts
		lst = []
		x = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		for i in x:
			if len(p_nuts) > len(x):
				print('force quit')
				break
			if i in p_nuts:
				lst += [i]
		nuts = lst
		bolts = lst


class Solution:

	def matchPairs(self, p_nuts, p_bolts, n):
		global nuts
		global bolts
		lst = []
		x = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		for i in x:
			if i in p_nuts or len(lst) > 10:
				lst += [i]
		nuts = lst
		bolts = lst


class Solution:

	def matchPairs(self, a, b, n):
		temp = []
		for i in range(len(b)):
			temp.append(ord(b[i]))
		temp.sort()
		for i in range(len(temp)):
			a[i] = b[i] = chr(temp[i])


class Solution:

	def hpartition(self, arr, left, right):
		pivot = arr[left]
		while True:
			while arr[left] < pivot:
				left += 1
			while arr[right] > pivot:
				right -= 1
			if left >= right:
				return left
			(arr[left], arr[right]) = (arr[right], arr[left])
		return left

	def quicksort(self, arr, left, right):
		if right > left:
			parti = self.hpartition(arr, left, right)
			self.quicksort(arr, left, parti)
			self.quicksort(arr, parti + 1, right)

	def matchPairs(self, nuts, bolts, n):
		self.quicksort(nuts, 0, len(nuts) - 1)
		self.quicksort(bolts, 0, len(nuts) - 1)
		return


class Solution:

	def hpartition(self, arr, low, high):
		pivot = arr[low]
		i = low
		j = high
		while True:
			while arr[i] < pivot:
				i += 1
			while arr[j] > pivot:
				j -= 1
			if i >= j:
				return i
			(arr[i], arr[j]) = (arr[j], arr[i])

	def quicksort(self, arr, left, right):
		if right > left:
			parti = self.hpartition(arr, left, right)
			self.quicksort(arr, left, parti)
			self.quicksort(arr, parti + 1, right)

	def matchPairs(self, nuts, bolts, n):
		self.quicksort(nuts, 0, len(nuts) - 1)
		self.quicksort(bolts, 0, len(nuts) - 1)
		return nuts


class Solution:

	def matchPairs(self, nuts, bots, n):
		a = '!#$%&*@^~'
		h = {'!': 1, '#': 2, '$': 3, '%': 4, '&': 5, '*': 6, '@': 7, '^': 8, '~': 9}
		for i in range(n):
			nuts[i] = h[nuts[i]]
			bots[i] = h[bots[i]]
		nuts.sort()
		bots.sort()
		for i in range(n):
			nuts[i] = a[nuts[i] - 1]
			bots[i] = a[bots[i] - 1]


class Solution:

	def matchPairs(self, nuts, bolts, n):
		nuts_hash = {}
		for (i, v) in enumerate(nuts):
			nuts_hash[v] = i
		bolts_hash = {}
		for (i, v) in enumerate(bolts):
			bolts_hash[v] = i
		i = 0
		for c in '!#$%&*@^~':
			if nuts_hash.get(c) != None and bolts_hash.get(c) != None:
				nuts[i] = c
				bolts[i] = c
				i += 1


class Solution:

	def matchPairs(self, nuts, bolts, n):
		lst = list('!#$%&*@^~')
		k = 0
		for i in lst:
			if i in bolts:
				nuts[k] = i
				k += 1
		k = 0
		for i in nuts:
			bolts[k] = i
			k += 1


from typing import List

def partition(arr: List[str], low: int, high: int, pivot: str) -> int:
	i = low
	j = low
	while j < high:
		if arr[j] < pivot:
			(arr[i], arr[j]) = (arr[j], arr[i])
			i += 1
		elif arr[j] == pivot:
			(arr[j], arr[high]) = (arr[high], arr[j])
			j -= 1
		j += 1
	(arr[i], arr[high]) = (arr[high], arr[i])
	return i

def matchPairs1(nuts: List[str], bolts: List[str], low: int, high: int) -> None:
	if low < high:
		pivot = partition(nuts, low, high, bolts[high])
		partition(bolts, low, high, nuts[pivot])
		matchPairs1(nuts, bolts, low, pivot - 1)
		matchPairs1(nuts, bolts, pivot + 1, high)

class Solution:

	def matchPairs(self, nuts, bolts, n):
		matchPairs1(nuts, bolts, 0, n - 1)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		for i in range(n):
			for j in range(i, n):
				if nuts[i] == bolts[j]:
					temp = bolts[j]
					bolts[j] = bolts[i]
					bolts[i] = temp
					break
		nuts.sort()
		bolts.sort()


class Solution:

	def matchPairs(self, nuts, bolts, n):
		(nd, bd) = ({}, {})
		for n in nuts:
			nd[n] = True
		for b in bolts:
			bd[b] = True
		nuts.clear()
		bolts.clear()
		a = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		for i in a:
			if nd.get(i) and bd.get(i):
				nuts.append(i)
				bolts.append(i)
		return (nuts, bolts)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		l = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		nd = {}
		bd = {}
		for i in nuts:
			if i not in nd:
				nd[i] = 1
			else:
				nd[i] += 1
		for i in bolts:
			if i not in bd:
				bd[i] = 1
			else:
				bd[i] += 1
		dl = {}
		for i in l:
			if i in nd and i in bd:
				k = min(bd[i], nd[i])
				dl[i] = k
		k = []
		for i in l:
			if i in dl:
				for j in range(dl[i]):
					k.append(i)
		nuts[:] = k
		bolts[:] = k


class Solution:

	def matchPairs(self, nuts, bolts, n):
		a = {'!': 0, '#': 1, '$': 2, '%': 3, '&': 4, '*': 5, '@': 6, '^': 7, '~': 8}
		s = {0: '!', 1: '#', 2: '$', 3: '%', 4: '&', 5: '*', 6: '@', 7: '^', 8: '~'}
		b = []
		c = []
		for i in range(len(nuts)):
			k = a[nuts[i]]
			p = a[bolts[i]]
			b.append(k)
			c.append(p)
		b.sort()
		c.sort()
		nuts.clear()
		bolts.clear()
		for i in range(len(b)):
			nuts.append(s[b[i]])
			bolts.append(s[c[i]])


class Solution:

	def matchPairs(self, nuts, bolts, n):
		d = {}
		for i in nuts:
			d[ord(i)] = i
		l = list(d.keys())
		l.sort()
		nuts.clear()
		for i in l:
			nuts.append(d[i])
		bolts.clear()
		bolts.extend(nuts)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		L = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		(N, B) = ([], [])
		for i in L:
			if i in nuts:
				N.append(i)
			if i in bolts:
				B.append(i)
		nuts.clear()
		bolts.clear()
		nuts.extend(N)
		bolts.extend(B)
		return ()


from collections import Counter

class Solution:

	def matchPairs(self, nuts, bolts, n):
		orde = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		j = 0
		l = Counter(nuts)
		for i in range(len(orde)):
			if orde[i] in l:
				nuts[j] = orde[i]
				bolts[j] = orde[i]
				j += 1


class Solution:

	def matchPairs(self, nuts, bolts, n):
		o = '!#$%&*@^~'
		dic = {}
		for i in range(len(o)):
			dic[o[i]] = i

		def helper(s, e, pi, arr):
			i = s
			while s < e:
				if dic[arr[s]] < pi:
					(arr[s], arr[i]) = (arr[i], arr[s])
					i += 1
				if dic[arr[s]] == pi:
					(arr[e], arr[s]) = (arr[s], arr[e])
					s -= 1
				s += 1
			(arr[e], arr[i]) = (arr[i], arr[e])
			return i

		def p(l, r, arr):
			if l < r:
				pi = helper(l, r, dic[arr[r]], arr)
				p(l, pi - 1, arr)
				p(pi + 1, r, arr)
		p(0, len(nuts) - 1, nuts)
		p(0, len(nuts) - 1, bolts)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		l = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		a = []
		for i in range(len(l)):
			if l[i] in nuts:
				a.append(l[i])
		for i in range(n):
			nuts[i] = a[i]
			bolts[i] = a[i]


class Solution:

	def matchPairs(self, nuts, bolts, n):
		elts = '! # $ % & * @ ^ ~'.split(' ')
		res = [e for e in elts if e in nuts and e in bolts]
		nuts.clear()
		bolts.clear()
		nuts.extend(res)
		bolts.extend(res)


class Solution:

	def matchPairs(self, nuts, bolts, n):
		order = ['!', '#', '$', '%', '&', '*', '@', '^', '~']
		hnuts = {i: j for i in order for j in [0] * 9}
		for ele in nuts:
			hnuts[ele] = 1
		res = []
		for i in order:
			if hnuts[i]:
				res.append(i)
		nuts[:] = res
		bolts[:] = res