Given two arrays: a1[0..n-1] of size n and a2[0..m-1] of size m. Task is to check whether a2[] is a subset of a1[] or not. Both the arrays can be sorted or unsorted. There can be duplicate elements.
 
Example 1:
Input:
a1[] = {11, 7, 1, 13, 21, 3, 7, 3}
a2[] = {11, 3, 7, 1, 7}
Output:
Yes
Explanation:
a2[] is a subset of a1[]
Example 2:
Input:
a1[] = {1, 2, 3, 4, 4, 5, 6}
a2[] = {1, 2, 4}
Output:
Yes
Explanation:
a2[] is a subset of a1[]
Example 3:
Input:
a1[] = {10, 5, 2, 23, 19}
a2[] = {19, 5, 3}
Output:
No
Explanation:
a2[] is not a subset of a1[]
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isSubset() which takes the array a1[], a2[], its size n and m as inputs and return "Yes" if arr2 is subset of arr1 else return "No" if arr2 is not subset of arr1.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 <= n,m <= 10^{5}
1 <= a1[i], a2[j] <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Complete search

Starter code: #User function Template for python3



def isSubset( a1, a2, n, m):

    

    

    



Solutions:
from collections import Counter

def isSubset(a1, a2, n, m):
	dic = Counter(a1)
	for i in a2:
		if i in dic:
			dic[i] -= 1
			if dic[i] < 0:
				return 'No'
		else:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	for i in a2:
		if i not in a1:
			return 'No'
		else:
			a1.remove(i)
	return 'Yes'


def isSubset(a1, a2, n, m):
	d1 = {}
	d2 = {}
	for i in a1:
		try:
			d1[i] += 1
		except:
			d1[i] = 1
	for i in a2:
		try:
			d2[i] += 1
		except:
			d2[i] = 1
	for (i, j) in d2.items():
		if i in d1 and j <= d1[i]:
			continue
		else:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	st1 = {}
	st2 = {}
	for i in range(n):
		st1[a1[i]] = st1.get(a1[i], 0) + 1
	for i in range(m):
		st2[a2[i]] = st2.get(a2[i], 0) + 1
	a = 0
	for i in range(m):
		if st2.get(a2[i]) <= st1.get(a2[i], 0):
			a += 1
	if a == m:
		return 'Yes'
	else:
		return 'No'


def isSubset(a1, a2, n, m):
	for number in a2:
		if number in a1:
			a1.remove(number)
		else:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	from collections import Counter
	m1 = Counter()
	for elem in a1:
		m1[elem] += 1
	for elem in a2:
		m1[elem] -= 1
	for i in m1:
		if m1[i] < 0:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	ha = {}
	for i in a1:
		ha[i] = ha.get(i, 0) + 1
	for i in a2:
		if i not in ha:
			return 'No'
		if ha[i] == 0:
			return 'No'
		if i in ha:
			ha[i] -= 1
	return 'Yes'


def isSubset(arr1, arr2, n, m):
	flag = True
	dict1 = {}
	dict2 = {}
	for num in arr1:
		dict1[num] = dict1.get(num, 0) + 1
	for num in arr2:
		dict2[num] = dict2.get(num, 0) + 1
	for (key, value) in dict2.items():
		if key not in dict1 or value > dict1[key]:
			flag = False
	if flag is True:
		return 'Yes'
	else:
		return 'No'


def isSubset(a1, a2, n, m):
	if m > n:
		return 'No'
	else:
		from collections import Counter
		a = Counter(a1)
		x = 0
		for i in a2:
			if i in a1:
				if a[i] == 0:
					return 'No'
					break
				a[i] = a[i] - 1
			else:
				x = x + 1
				return 'No'
				break
		if x == 0:
			return 'Yes'


def isSubset(a1, a2, n, m):
	if m > n:
		return 'No'
	else:
		x = 0
		for i in a2:
			if i not in a1:
				x = x + 1
				return 'No'
				break
			else:
				a1.remove(i)
		if x == 0:
			return 'Yes'


def isSubset(a1, a2, n, m):
	a1.sort()
	a2.sort()
	i = 0
	j = 0
	for x in range(n):
		if a1[i] == a2[j]:
			i += 1
			if m == j + 1:
				return 'Yes'
			j += 1
		elif a1[i] != a2[j]:
			i += 1
	return 'No'


def isSubset(a1, a2, n, m):
	a = list(a1)
	b = list(a2)
	a.sort()
	b.sort()
	for x in b:
		if x not in a:
			return 'No'
		else:
			a.remove(x)
	return 'Yes'


def isSubset(a1, a2, n, m):
	a = list(a1)
	b = list(a2)
	a.sort()
	b.sort()
	if m > n:
		return 'No'
	if b[0] not in a:
		return 'No'
	else:
		first_index = a.index(b[0])
		ai = first_index
		bi = 0
		while bi < m:
			if a[ai] != b[bi] and a[ai] > b[bi]:
				return 'No'
			elif a[ai] != b[bi] and a[ai] < b[bi]:
				ai += 1
			else:
				bi += 1
				ai += 1
		return 'Yes'


def isSubset(a1, a2, n, m):
	fl = 0
	for i in a2:
		if i not in a1:
			fl = 1
			return 'No'
		else:
			del a1[a1.index(i)]
	if fl == 0:
		return 'Yes'


def isSubset(a1, a2, n, m):
	dict = {}
	for i in a2:
		dict[i] = dict.get(i, 0) + 1
	count = 0
	for i in a1:
		if i in dict and dict[i] > 0:
			count += 1
			dict[i] -= 1
	return 'Yes' if count == m else 'No'


from collections import Counter

def isSubset(a1, a2, n, m):
	for i in a2:
		if i not in a1:
			return 'No'
		else:
			a1.remove(i)
	return 'Yes'


def isSubset(a1, a2, n, m):
	m_dict = {}
	for i in a2:
		if i in m_dict:
			m_dict[i] += 1
		else:
			m_dict[i] = 1
	for j in a1:
		if j in m_dict and m_dict[j] > 0:
			m_dict[j] -= 1
	for x in m_dict.values():
		if x != 0:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	from collections import Counter
	a = Counter(a1)
	b = Counter(a2)
	for (i, j) in b.items():
		if i in a:
			if a[i] >= b[i]:
				continue
			else:
				return 'No'
		else:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	d = {}
	for i in a1:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in a2:
		if i in d:
			if d[i] == 0:
				d.pop(i)
			if i in d:
				d[i] -= 1
		if i not in d:
			return 'No'
	return 'Yes'


import math

def isSubset(a1, a2, n, m):
	count = 0
	for i in a2:
		if i not in a1:
			return 'No'
		else:
			a1.remove(i)
	return 'Yes'


def isSubset(a1, a2, n, m):
	d = {}
	for i in a1:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in a2:
		if i not in d:
			return 'No'
		elif d[i] == 1:
			del d[i]
		else:
			d[i] -= 1
	return 'Yes'


def isSubset(a1, a2, n, m):
	count = 1
	for i in range(m):
		if a2[i] in a1:
			count = count * 1
			a1.remove(a2[i])
		else:
			count = 0
			break
	if count == 1:
		return 'Yes'
	else:
		return 'No'


def isSubset(a1, a2, n, m):
	for i in a2:
		if i not in a1 or a2.count(i) > a1.count(i):
			return 'No'
	return 'Yes'


from collections import Counter

def isSubset(a1, a2, n, m):
	c_a1 = Counter(a1)
	c_a2 = Counter(a2)
	for (i, x) in c_a2.items():
		if i not in c_a1 or x > c_a1[i]:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	dict1 = {}
	for i in a1:
		dict1[i] = dict1.get(i, 0) + 1
	for j in a2:
		if j not in dict1 or dict1[j] <= 0:
			return 'No'
		else:
			dict1[j] -= 1
	return 'Yes'


def isSubset(a1, a2, n, m):
	dict_a1 = {}
	for i in a1:
		dict_a1[i] = dict_a1.get(i, 0) + 1
	for element in a2:
		if element not in dict_a1 or dict_a1[element] <= 0:
			return 'No'
		else:
			dict_a1[element] -= 1
	return 'Yes'


def isSubset(a1, a2, n, m):
	mp = {}
	for i in a1:
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
	for i in a2:
		if i not in mp or mp[i] < 1:
			return 'No'
		else:
			mp[i] -= 1
	return 'Yes'


def isSubset(a1, a2, n, m):
	if m == 0:
		return 'Yes'
	if m > n:
		return 'No'
	(count1, count2) = ({}, {})
	for i in a1:
		count1[i] = 1 + count1.get(i, 0)
	for j in a2:
		count2[j] = 1 + count2.get(j, 0)
	for ele in a2:
		if ele not in a1:
			return 'No'
		elif ele in a1 and count1[ele] < count2[ele]:
			return 'No'
		else:
			continue
	return 'Yes'


from collections import defaultdict

def isSubset(a1, a2, n, m):
	dic1 = defaultdict(lambda : 0)
	dic2 = defaultdict(lambda : 0)
	for i in a1:
		dic1[i] += 1
	for i in a2:
		dic2[i] += 1
	for i in dic2:
		if dic1[i] < dic2[i]:
			return 'No'
	return 'Yes'


def isSubset(l1, l2, n, m):
	c = 0
	if l1 == l2:
		return 'Yes'
	for i in l2:
		if i in l1:
			l1.remove(i)
		else:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	if m > n:
		return 'No'
	a1.sort()
	a2.sort()
	i = 0
	j = 0
	c = 0
	while i < n and j < m:
		if a1[i] == a2[j]:
			i += 1
			j += 1
			c += 1
		elif a1[i] < a2[j]:
			i += 1
		else:
			j += 1
	if c == m:
		return 'Yes'
	else:
		return 'No'


def isSubset(a1, a2, n, m):
	if m > n:
		return 'No'
	element_count = {}
	for num in a1:
		if num in element_count:
			element_count[num] = element_count[num] + 1
		else:
			element_count[num] = 1
	for num in a2:
		if num not in element_count:
			return 'No'
		else:
			element_count[num] = element_count[num] - 1
			if element_count[num] == 0:
				del element_count[num]
	return 'Yes'


def isSubset(a1, a2, n, m):
	for num in a2:
		if num not in a1:
			return 'No'
		a1.remove(num)
	return 'Yes'


def isSubset(a1, a2, n, m):
	for e in a2:
		try:
			a1.remove(e)
		except:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	for i in a2:
		if i in a1 and a2.count(i) <= a1.count(i):
			pass
		else:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	ans = {}
	for i in a1:
		ans[i] = 1 + ans.get(i, 0)
	for i in a2:
		ans[i] = ans.get(i, 0) - 1
		if ans[i] < 0:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	hashm = {}
	for j in range(n):
		if a1[j] not in hashm:
			hashm[a1[j]] = 1
		else:
			hashm[a1[j]] += 1
	for i in range(m):
		if a2[i] not in a1 or hashm[a2[i]] == 0:
			return 'No'
		else:
			hashm[a2[i]] -= 1
	return 'Yes'


def isSubset(a1, a2, n, m):
	arrayMap = {}
	for ele in a1:
		if ele in arrayMap:
			arrayMap[ele] += 1
		else:
			arrayMap[ele] = 1
	for ele in a2:
		if ele in arrayMap:
			arrayMap[ele] -= 1
			if arrayMap[ele] == 0:
				del arrayMap[ele]
		elif ele not in arrayMap:
			return 'No'
	return 'Yes'


from collections import Counter

def isSubset(a1, a2, n, m):
	count_a1 = Counter(a1)
	count_a2 = Counter(a2)
	for key in count_a2:
		if key not in count_a1 or count_a2[key] > count_a1[key]:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	for i in range(m):
		if a2.count(a2[i]) > a1.count(a2[i]):
			return 'No'
	return 'Yes'


import itertools
from itertools import combinations

def isSubset(a1, a2, n, m):
	for i in range(m):
		if a2[i] in a1:
			a1.remove(a2[i])
		else:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	obj1 = {}
	obj2 = {}
	for item in a1:
		if item not in obj1:
			obj1[item] = 1
		else:
			obj1[item] += 1
	for item in a2:
		if item not in obj2:
			obj2[item] = 1
		else:
			obj2[item] += 1
	for key in obj2:
		if key not in obj1 or obj2[key] > obj1[key]:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	flag = False
	for i in a2:
		if i in a1:
			a1.remove(i)
			flag = True
		else:
			flag = False
			return 'No'
	if flag:
		return 'Yes'
	else:
		return 'No'


from collections import Counter

def isSubset(a1, a2, n, m):
	c1 = Counter(a1)
	c2 = Counter(a2)
	for num in c2:
		if num not in c1 or c1[num] < c2[num]:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	flag = False
	for i in range(len(a2)):
		if a2.count(a2[i]) <= a1.count(a2[i]):
			flag = True
		else:
			flag = False
			break
	if flag == True:
		return 'Yes'
	else:
		return 'No'


def isSubset(a1, a2, n, m):
	check = 0
	for i in a2:
		if i in a1 and a2.count(i) <= a1.count(i):
			check += 1
		else:
			return 'No'
	if check == len(a2):
		return 'Yes'


def isSubset(a1, a2, n, m):
	hmap1 = {}
	hmap2 = {}
	for i in a1:
		if i in hmap1:
			hmap1[i] = hmap1[i] + 1
		else:
			hmap1[i] = 1
	for i in a2:
		if i in hmap2:
			hmap2[i] = hmap2[i] + 1
		else:
			hmap2[i] = 1
	for k in hmap2.keys():
		if k in hmap1 and hmap1[k] >= hmap2[k]:
			continue
		else:
			return 'No'
	return 'Yes'


from collections import defaultdict

def isSubset(a1, a2, n, m):
	d = defaultdict(lambda : 0)
	for i in a1:
		d[i] += 1
	for i in a2:
		d[i] -= 1
	ret = 'Yes'
	for k in d:
		if d[k] < 0:
			ret = 'No'
			break
	return ret


def isSubset(a1, a2, n, m):
	(dict, c) = ({}, 0)
	for el in a1:
		if el in dict:
			dict[el] += 1
		else:
			dict[el] = 1
	for el in a2:
		if el in dict:
			dict[el] -= 1
			if dict[el] == 0:
				del dict[el]
			c += 1
	if c == len(a2):
		return 'Yes'
	return 'No'


def isSubset(a1, a2, n, m):
	for x in range(0, m):
		flag = 0
		for y in a1:
			if a2[x] == y:
				flag = 1
				a1.remove(a2[x])
				break
		if flag == 0:
			break
	if flag == 0:
		return 'No'
	else:
		return 'Yes'


def isSubset(a1, a2, n, m):
	seen = {}
	if m > n:
		return 'No'
	else:
		for element in a1:
			if element in seen:
				seen[element] += 1
			else:
				seen[element] = 1
		for x in a2:
			if x in seen and seen[x] > 0:
				seen[x] -= 1
			else:
				return 'No'
		return 'Yes'


def isSubset(a1, a2, n, m):
	count = 0
	d = {}
	d1 = {}
	for i in a2:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	for i in a1:
		if i in d1.keys():
			d1[i] += 1
		else:
			d1[i] = 1
	for i in a2:
		try:
			if d1[i] >= d[i]:
				count += 1
		except:
			return 'No'
	if count == m:
		return 'Yes'
	else:
		return 'No'


def isSubset(a1, a2, n, m):
	a1.sort()
	for k in a2:
		if k not in a1:
			return 'No'
		else:
			a1.remove(k)
	else:
		return 'Yes'


def isSubset(a1, a2, n, m):
	container = dict()
	if len(a1) is 0 or len(a2) is 0:
		return 'No'
	for ele in a1:
		if ele in container:
			container[ele] = container[ele] + 1
		else:
			container[ele] = 1
	for ele in a2:
		if ele not in container:
			return 'No'
		else:
			container[ele] -= 1
			if container[ele] < 0:
				return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	count_a1 = {}
	for num in a1:
		count_a1[num] = count_a1.get(num, 0) + 1
	for num in a2:
		if num not in count_a1 or count_a1[num] == 0:
			return 'No'
		count_a1[num] -= 1
	return 'Yes'


def isSubset(a1, a2, n, m):
	x = 0
	s = 0
	for i in range(m):
		s += 1
		if a2[i] in a1:
			x += 1
			a1.remove(a2[i])
		else:
			x -= 0
		if x != s:
			break
	if x == m:
		k = 'Yes'
	else:
		k = 'No'
	return k


def isSubset(a1, a2, n, m):
	if m > n:
		return 'No'
	elementi_A = {}
	for i in range(n):
		if a1[i] not in elementi_A:
			elementi_A[a1[i]] = 1
		else:
			elementi_A[a1[i]] += 1
	for i in range(m):
		if a2[i] not in elementi_A:
			return 'No'
		else:
			elementi_A[a2[i]] -= 1
			if elementi_A[a2[i]] == 0:
				del elementi_A[a2[i]]
	return 'Yes'


def isSubset(l1, l2, n, m):
	d1 = {}
	d2 = {}
	for i in l2:
		if i in d2:
			d2[i] += 1
		else:
			d2[i] = 1
	for i in l1:
		if i in d1:
			d1[i] += 1
		else:
			d1[i] = 1
	for i in d2:
		if i in d1:
			if not d1[i] - d2[i] >= 0:
				return 'No'
		else:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	dict1 = {}
	dict2 = {}
	for i in a2:
		if i not in dict2:
			dict2[i] = 1
		else:
			dict2[i] += 1
	for i in a1:
		if i not in dict1:
			dict1[i] = 1
		else:
			dict1[i] += 1
	for i in a2:
		if i not in dict1:
			return 'No'
		if dict2[i] > dict1[i]:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	for i in a2:
		b = len(a1)
		for j in range(b):
			if i == a1[j]:
				a1.remove(i)
				j -= 1
				break
		if j == b - 1:
			return 'No'
	return 'Yes'


def isSubset(a1, a2, n, m):
	a1.sort()
	a2.sort()
	j = 0
	for i in a1:
		if j == m:
			break
		if i == a2[j]:
			j = j + 1
		elif i < a2[j]:
			continue
		else:
			break
	return 'Yes' if j == m else 'No'