What would be the solution to this problem that is faster than O(N^2). Would it be possible to go faster than O(nlogn). My approach was to solve it by appending the arrays together and sorting them. Then I would have a dictionary for both teamA and teamB that would allow me to look up matches in each array in constant space. I would then increment my counter if it is part of teamA and append the count to my result array when it is part of teamB.
def foot(teamA, teamB):
adic = Counter(teamA)
bdic = Counter(teamB)
res = []
sortedteams = []
for i in teamA:
sortedteams.append(i)
for j in teamB:
if j not in adic:
sortedteams.append(j)
sortedteams.sort()
count = 0
for n in sortedteams:
if n in adic:
count += 1
if n in bdic:
res.append(count)
return res
print(foot([2, 10, 5, 4, 8], [3, 1, 7, 8]))Example solution
teamA = [2, 10, 5, 4, 8],
teamB = [3, 1, 7, 8]
output = [1, 0, 3, 4]Comments (9)