Union of two arrays can be defined as the common and distinct elements in the two arrays.
Given two sorted arrays of size n and m respectively, find their union.
Example 1:
Input: 
n = 5, arr1[] = {1, 2, 3, 4, 5}  
m = 3, arr2 [] = {1, 2, 3}
Output: 1 2 3 4 5
Explanation: Distinct elements including 
both the arrays are: 1 2 3 4 5.
 
Example 2:
Input: 
n = 5, arr1[] = {2, 2, 3, 4, 5}  
m = 5, arr2[] = {1, 1, 2, 3, 4}
Output: 1 2 3 4 5
Explanation: Distinct elements including 
both the arrays are: 1 2 3 4 5.
 
Example 3:
Input:
n = 5, arr1[] = {1, 1, 1, 1, 1}
m = 5, arr2[] = {2, 2, 2, 2, 2}
Output: 1 2
Explanation: Distinct elements including 
both the arrays are: 1 2.
Your Task: 
You do not need to read input or print anything. Complete the function findUnion() that takes two arrays arr1[], arr2[], and their size n and m as input parameters and returns a list containing the union of the two arrays. 
 
Expected Time Complexity: O(n+m).
Expected Auxiliary Space: O(n+m).
 
Constraints:
1 <= n, m <= 10^{5}
1 <= arr[i], brr[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    

    #Function to return a list containing the union of the two arrays.

    def findUnion(self,a,b,n,m):

        '''

        :param a: given sorted array a

        :param n: size of sorted array a

        :param b: given sorted array b

        :param m: size of sorted array b

        :return:  The union of both arrays as a list

        '''

        # code here 

Solutions:
class Solution:

	def findUnion(self, a, b, n, m):
		union_li = list()
		(i, j) = (0, 0)
		while i < n and j < m:
			while i + 1 < n and a[i + 1] == a[i]:
				i += 1
			while j + 1 < m and b[j + 1] == b[j]:
				j += 1
			if a[i] < b[j]:
				union_li.append(a[i])
				i += 1
			elif b[j] < a[i]:
				union_li.append(b[j])
				j += 1
			else:
				union_li.append(b[j])
				j += 1
				i += 1
		while i < n:
			while i + 1 < n and a[i + 1] == a[i]:
				i += 1
			union_li.append(a[i])
			i += 1
		while j < m:
			while j + 1 < m and b[j + 1] == b[j]:
				j += 1
			union_li.append(b[j])
			j += 1
		return union_li


class Solution:

	def findUnion(self, a, b, n, m):
		l1 = 0
		l2 = 0
		freq_map = {}
		ans = []
		while l1 < n and l2 < m:
			if a[l1] <= b[l2]:
				if a[l1] not in freq_map:
					freq_map[a[l1]] = 1
					ans.append(a[l1])
				l1 += 1
			else:
				if b[l2] not in freq_map:
					freq_map[b[l2]] = 1
					ans.append(b[l2])
				l2 += 1
		while l1 < n:
			if a[l1] not in freq_map:
				freq_map[a[l1]] = 1
				ans.append(a[l1])
			l1 += 1
		while l2 < m:
			if b[l2] not in freq_map:
				freq_map[b[l2]] = 1
				ans.append(b[l2])
			l2 += 1
		return ans


class Solution:

	def findUnion(self, a, b, n, m):
		list1 = a + b
		set1 = set(list1)
		list1 = list(set1)
		list1.sort()
		return list1


class Solution:

	def findUnion(self, arr1, arr2, n, m):
		arr1 = arr1 + arr2
		s = list(set(arr1))
		ans = []
		for i in range(len(s)):
			ans.append(s[i])
		ans.sort()
		return ans


class Solution:

	def findUnion(self, a, b, n, m):
		return sorted(set(a + b))


class Solution:

	def findUnion(self, a, b, n, m):
		c = a + b
		s = list(set(c))
		s.sort()
		return s


class Solution:

	def findUnion(self, a, b, n, m):
		arr = []
		arr = a + b
		arr = set(arr)
		arr = list(arr)
		arr.sort()
		return arr


class Solution:

	def findUnion(self, a, b, n, m):
		result_set = set(a + b)
		result_list = sorted(list(result_set))
		return result_list


class Solution:

	def findUnion(self, arr1, arr2, n, m):
		i = 0
		j = 0
		union = []
		while i < n and j < m:
			while i + 1 < n and a[i + 1] == a[i]:
				i += 1
			while j + 1 < m and b[j + 1] == b[j]:
				j += 1
			if a[i] < b[j]:
				union.append(a[i])
				i += 1
			elif a[i] > b[j]:
				union.append(b[j])
				j += 1
			else:
				union.append(a[i])
				i += 1
				j += 1
		while i < n:
			while i + 1 < n and a[i + 1] == a[i]:
				i += 1
			union.append(a[i])
			i += 1
		while j < m:
			while j + 1 < m and b[j + 1] == b[j]:
				j += 1
			union.append(b[j])
			j += 1
		return union


class Solution:

	def findUnion(self, a, b, n, m):
		temp = a + b
		my_set = set(temp)
		my_list = sorted(list(my_set))
		return my_list


class Solution:

	def findUnion(self, a, b, n, m):
		i = 0
		j = 0
		res = []
		while i < n and j < m:
			if a[i] == b[j]:
				if len(res) == 0:
					res.append(a[i])
					i += 1
					j += 1
				elif res[-1] != a[i]:
					res.append(a[i])
					i += 1
					j += 1
				else:
					i += 1
					j += 1
			elif a[i] < b[j]:
				if len(res) == 0:
					res.append(a[i])
					i += 1
				elif res[-1] != a[i]:
					res.append(a[i])
					i += 1
				else:
					i += 1
			elif b[j] < a[i]:
				if len(res) == 0:
					res.append(b[j])
					j += 1
				elif res[-1] != b[j]:
					res.append(b[j])
					j += 1
				else:
					j += 1
		while i < n:
			if res[-1] != a[i]:
				res.append(a[i])
				i += 1
			else:
				i += 1
		while j < m:
			if res[-1] != b[j]:
				res.append(b[j])
				j += 1
			else:
				j += 1
		return res


class Solution:

	def findUnion(self, a, b, n, m):
		l = a + b
		l = set(l)
		l1 = list(l)
		l1.sort()
		return l1


class Solution:

	def findUnion(self, a, b, n, m):
		i = 0
		j = 0
		union = []
		while i < n and j < m:
			if a[i] <= b[j]:
				if len(union) == 0 or union[-1] != a[i]:
					union.append(a[i])
				i += 1
			else:
				if len(union) == 0 or union[-1] != b[j]:
					union.append(b[j])
				j += 1
		while i < n:
			if len(union) == 0 or union[-1] != a[i]:
				union.append(a[i])
			i += 1
		while j < m:
			if len(union) == 0 or union[-1] != b[j]:
				union.append(b[j])
			j += 1
		return union


class Solution:

	def findUnion(self, a, b, n, m):
		c = set(a)
		d = set(b)
		e = c.union(d)
		return sorted(e)


class Solution:

	def findUnion(self, a, b, n, m):
		l = set()
		for i in range(max(n, m)):
			if i < n:
				l.add(a[i])
			if i < m:
				l.add(b[i])
		l = list(l)
		l.sort()
		return l


class Solution:

	def findUnion(self, a, b, n, m):
		c = a + b
		s = {}
		s = set(s)
		for i in c:
			s.add(i)
		s = list(s)
		s.sort()
		return s


class Solution:

	def findUnion(self, array1, array2, n, m):
		array = array1 + array2
		array = list(set(array))
		array.sort()
		return array


class Solution:

	def findUnion(self, a, b, n, m):
		for i in b:
			a.append(i)
		return sorted(set(a))


class Solution:

	def findUnion(self, arr1, arr2, n, m):
		mp1 = {}
		res = []
		for i in range(len(arr1)):
			if arr1[i] not in mp1:
				mp1[arr1[i]] = 1
				res.append(arr1[i])
		for j in range(len(arr2)):
			if arr2[j] not in mp1:
				mp1[arr2[j]] = 1
				res.append(arr2[j])
		res.sort()
		return res


class Solution:

	def findUnion(self, a, b, n, m):
		hashed = {}
		for i in a:
			hashed[i] = 1 + hashed.get(i, 0)
		for j in b:
			hashed[j] = 1 + hashed.get(j, 0)
		res = []
		for k in hashed:
			res.append(k)
		res.sort()
		return res


class Solution:

	def findUnion(self, a, b, n, m):
		res = []
		(i, j) = (int(0), int(0))
		while i < n and j < m:
			if a[i] == b[j]:
				res.append(a[i])
				i = i + 1
				j = j + 1
			elif a[i] < b[j]:
				res.append(a[i])
				i = i + 1
			else:
				res.append(b[j])
				j = j + 1
		if i < n:
			for k in range(i, n):
				res.append(a[k])
		if j < m:
			for k in range(j, m):
				res.append(b[k])
		ress = []
		for i in range(len(res) - 1):
			if res[i] != res[i + 1]:
				ress.append(res[i])
		if res[-1] != ress[-1]:
			ress.append(res[-1])
		return ress


class Solution:

	def add_array(self, temp, nu):
		if len(temp) > 0 and temp[-1] == nu:
			return
		temp.append(nu)

	def findUnion(self, a, b, n, m):
		i = 0
		j = 0
		temp = []
		while i < n and j < m:
			if a[i] == b[j]:
				self.add_array(temp, a[i])
				i += 1
				j += 1
			elif a[i] < b[j]:
				self.add_array(temp, a[i])
				i += 1
			else:
				self.add_array(temp, b[j])
				j += 1
		while i < n:
			self.add_array(temp, a[i])
			i += 1
		while j < m:
			self.add_array(temp, b[j])
			j += 1
		return temp


class Solution:

	def findUnion(self, a, b, n, m):
		temp = set()
		for i in a:
			temp.add(i)
		for i in b:
			temp.add(i)
		return list(sorted(temp))


class Solution:

	def findUnion(self, a, b, n, m):
		hash_set = {}
		for ele in a:
			if ele not in hash_set:
				hash_set[ele] = 1
		for ele in b:
			if ele not in hash_set:
				hash_set[ele] = 1
		return sorted(hash_set.keys())


class Solution:

	def findUnion(self, a, b, n, m):
		ans = []
		sa = set()
		for i in range(0, n):
			sa.add(a[i])
		for i in range(0, m):
			sa.add(b[i])
		for i in sa:
			ans.append(i)
		ans = sorted(ans)
		return ans


class Solution:

	def findUnion(self, a, b, n, m):
		s = set()
		l = [min(a[0], b[0])]
		i = 0
		j = 0
		while i < n and j < m:
			if a[i] < b[j]:
				if l[-1] != a[i]:
					l.append(a[i])
				i += 1
			elif b[j] <= a[i]:
				if l[-1] != b[j]:
					l.append(b[j])
				j += 1
		while i < n:
			if l[-1] != a[i]:
				l.append(a[i])
			i += 1
		while j < m:
			if l[-1] != b[j]:
				l.append(b[j])
			j += 1
		return l


class Solution:

	def findUnion(self, a, b, n, m):
		c = a + b
		c.sort()
		x = []
		for i in range(0, len(c)):
			if i == 0 or c[i] != c[i - 1]:
				x.append(c[i])
		return x


class Solution:

	def findUnion(self, a, b, n, m):
		hashmap = {}
		for i in a:
			hashmap[i] = 1 + hashmap.get(i, 0)
		for i in b:
			hashmap[i] = 1 + hashmap.get(i, 0)
		return sorted(list(hashmap.keys()))


class Solution:

	def findUnion(self, a, b, n, m):
		s = set()
		for i in a:
			s.add(i)
		for i in b:
			s.add(i)
		return sorted(s)


class Solution:

	def findUnion(self, a, b, n, m):
		s = list(set(a))
		t = list(set(b))
		lst = list(set(list(set(a)) + list(set(b))))
		lst.sort()
		return lst


class Solution:

	def findUnion(self, a, b, n, m):
		for x in b:
			a.append(x)
		d = dict.fromkeys(a)
		return sorted(list(d))


class Solution:

	def findUnion(self, a, b, n, m):
		r = set(a).union(set(b))
		re = list(r)
		re.sort()
		return re


class Solution:

	def findUnion(self, a, b, n, m):
		s1 = set(a)
		s2 = set(b)
		s = s1.union(s2)
		return sorted(s)


class Solution:

	def findUnion(self, a, b, n, m):
		set1 = set(a)
		set2 = set(b)
		result = list(set1.union(set2))
		result.sort()
		return result


class Solution:

	def findUnion(self, a, b, n, m):
		i = 0
		j = 0
		c = 0
		ele = min(a[0], b[0])
		out = [ele]
		while i < n and j < m:
			if a[i] >= b[j]:
				if out[c] != b[j]:
					out.append(b[j])
					c += 1
				j += 1
			else:
				if out[c] != a[i]:
					out.append(a[i])
					c += 1
				i += 1
		while i < n:
			if out[c] != a[i]:
				out.append(a[i])
				c += 1
			i += 1
		while j < m:
			if out[c] != b[j]:
				out.append(b[j])
				c += 1
			j += 1
		return out


class Solution:

	def findUnion(self, a, b, n, m):
		result = [-1]
		index1 = index2 = 0
		while index1 < n and index2 < m:
			if a[index1] < b[index2]:
				if a[index1] != result[-1]:
					result.append(a[index1])
				index1 += 1
			else:
				if b[index2] != result[-1]:
					result.append(b[index2])
				index2 += 1
		while index1 < n:
			if a[index1] != result[-1]:
				result.append(a[index1])
			index1 += 1
		while index2 < m:
			if b[index2] != result[-1]:
				result.append(b[index2])
			index2 += 1
		result.pop(0)
		return result


class Solution:

	def findUnion(self, a, b, n, m):
		(i, j) = (0, 0)
		ans = []
		while i < n and j < m:
			if a[i] > b[j]:
				if len(ans) == 0 or ans[-1] != b[j]:
					ans.append(b[j])
				j += 1
			elif a[i] < b[j]:
				if len(ans) == 0 or ans[-1] != a[i]:
					ans.append(a[i])
				i += 1
			else:
				if len(ans) == 0 or ans[-1] != a[i]:
					ans.append(a[i])
				i += 1
				j += 1
		for d in range(i, n):
			if len(ans) == 0 or ans[-1] != a[d]:
				ans.append(a[d])
		for k in range(j, m):
			if len(ans) == 0 or ans[-1] != b[k]:
				ans.append(b[k])
		return ans


class Solution:

	def findUnion(self, a, b, n, m):
		st = set()
		for i in a:
			st.add(i)
		for j in b:
			st.add(j)
		union = list(st)
		union.sort()
		return union


class Solution:

	def findUnion(self, a, b, n, m):
		smallest_size = min(n, m)
		prev = -1
		i = 0
		j = 0
		ans = []
		while i < n and j < m:
			min_t = min(a[i], b[j])
			if min_t > prev:
				ans.append(min_t)
				prev = min_t
			while i < n and a[i] == min_t:
				i += 1
			while j < m and b[j] == min_t:
				j += 1
		while i < n:
			t = a[i]
			if t > prev:
				ans.append(t)
				prev = t
			while i < n and a[i] == t:
				i += 1
		while j < m:
			t = b[j]
			if t > prev:
				ans.append(t)
				prev = t
			while j < m and b[j] == t:
				j += 1
		return ans


class Solution:

	def findUnion(self, a, b, n, m):
		x = set(a)
		y = set(b)
		z = x.union(y)
		z = list(z)
		z.sort()
		return z


class Solution:

	def findUnion(self, a, b, n, m):
		i = 0
		j = 0
		ans = []
		while i < n and j < m:
			if a[i] < b[j]:
				if not ans:
					ans.append(a[i])
				elif a[i] > ans[-1]:
					ans.append(a[i])
				while i < n and a[i] == ans[-1]:
					i += 1
				while j < m and b[j] == ans[-1]:
					j += 1
			else:
				if not ans:
					ans.append(b[j])
				elif b[j] > ans[-1]:
					ans.append(b[j])
				while i < n and a[i] == ans[-1]:
					i += 1
				while j < m and b[j] == ans[-1]:
					j += 1
		while i < n:
			if a[i] > ans[-1]:
				ans.append(a[i])
			i += 1
		while j < m:
			if b[j] > ans[-1]:
				ans.append(b[j])
			j += 1
		return ans


class Solution:

	def findUnion(self, a, b, n, m):
		l = []
		s1 = list(set(a))
		s3 = set(a)
		for i in s1:
			l.append(i)
		s2 = list(set(b))
		for i in s2:
			if i not in s3:
				l.append(i)
		l.sort()
		return l


class Solution:

	def findUnion(self, a, b, n, m):
		s = 0
		t = 0
		j = 0
		k = 0
		arr = []
		if a[0] < b[0]:
			arr.append(a[0])
			j += 1
		elif a[0] > b[0]:
			arr.append(b[0])
			k += 1
		else:
			arr.append(a[0])
			j += 1
			k += 1
		for i in range(n + m):
			if j == n and k != m:
				if b[k] != arr[-1]:
					arr.append(b[k])
				k += 1
			elif k == m and j != n:
				if a[j] != arr[-1]:
					arr.append(a[j])
				j += 1
			elif k == m and j == n:
				return arr
			elif a[j] != b[k] and a[j] < b[k]:
				if a[j] != arr[-1]:
					arr.append(a[j])
				j += 1
			elif a[j] != b[k] and a[j] > b[k]:
				if b[k] != arr[-1]:
					arr.append(b[k])
				k += 1
			elif a[j] == b[k]:
				if a[j] != arr[-1]:
					arr.append(a[j])
				j += 1
				k += 1


class Solution:

	def findUnion(self, a, b, n, m):
		s = set(a + b)
		lis = []
		for x in s:
			lis.append(x)
		lis.sort()
		return lis


class Solution:

	def findUnion(self, a, b, n, m):
		arr = []
		i = 0
		j = 0
		while i < n and j < m:
			if a[i] == b[j]:
				if arr == [] or a[i] != arr[-1]:
					arr.append(a[i])
				i += 1
				j += 1
			elif a[i] < b[j]:
				if arr == [] or a[i] != arr[-1]:
					arr.append(a[i])
				i += 1
			elif a[i] > b[j]:
				if arr == [] or b[j] != arr[-1]:
					arr.append(b[j])
				j += 1
		while i < n:
			if a[i] != arr[-1]:
				arr.append(a[i])
			i += 1
		while j < m:
			if b[j] != arr[-1]:
				arr.append(b[j])
			j += 1
		return arr


class Solution:

	def findUnion(self, a, b, n, m):
		arr = a + b
		setArr = sorted(set(arr))
		return list(setArr)


class Solution:

	def findUnion(self, a, b, n, m):
		ans = []
		newarr = []
		(x, y) = (0, 0)
		while x < n and y < m:
			if a[x] <= b[y]:
				newarr.append(a[x])
				x = x + 1
			else:
				newarr.append(b[y])
				y = y + 1
		while x < n:
			newarr.append(a[x])
			x = x + 1
		while y < m:
			newarr.append(b[y])
			y = y + 1
		if len(newarr) == 0:
			return []
		ans.append(newarr[0])
		for i in range(1, len(newarr)):
			if newarr[i] != newarr[i - 1]:
				ans.append(newarr[i])
		return ans


class Solution:

	def findUnion(self, a, b, n, m):
		merge_arr = []
		i = 0
		j = 0
		merge_arr.append(min(a[i], b[j]))
		while i < len(a) and j < len(b):
			if a[i] <= b[j]:
				if merge_arr[-1] != a[i]:
					merge_arr.append(a[i])
				i += 1
			else:
				if merge_arr[-1] != b[j]:
					merge_arr.append(b[j])
				j += 1
		while i < len(a):
			if merge_arr[-1] != a[i]:
				merge_arr.append(a[i])
			i += 1
		while j < len(b):
			if merge_arr[-1] != b[j]:
				merge_arr.append(b[j])
			j += 1
		return merge_arr