This is the algorithm of this problem: Write a function that takes two arrays as input, each array contains a list of A-Z; your program should return True if the 2nd array is a subset of 1st array, or False if not.
JavaScript
x
17
17
1
# Python 3 program to find whether an array
2
3
def isSubset(arr1, arr2):
4
i = 0
5
for i in range(len(arr2)):
6
if(arr2[i] not in arr1):
7
return False
8
return True
9
10
arr1 = ["A", "B", "C", "D", "E", "F"]
11
arr2 = ["C", "A", "A"]
12
13
if(isSubset(arr1, arr2)):
14
print("arr2[] is a subset of arr1[] ")
15
else:
16
print("arr2[] is not a subset of arr1[]")
17
Advertisement
Answer
The complexity of your algorithm is O(n*k)
, where n
and k
is length of arrays. You have one loop inside another one and search in the list takes O(n)
JavaScript
1
3
1
for i in range(len(arr2)):
2
if(arr2[i] not in arr1) # inner loop because of `in` with `O(n)` complexity
3
You can optimize your algorithm:
JavaScript
1
10
10
1
s = set()
2
for el in arr1:
3
s.add(el)
4
5
for el in arr2:
6
if el not in s:
7
return False
8
9
return True
10
In this case the time complexity is O(n+k)
, where n
and k
is length of arrays. Search in the set
(and dict
has O(1)
time complexity).
But is this case you need an additional space for set
. So new algorithm has O(n)
space complexity while original one – O(1)
.