HackerRank Ransom Note challenge

Question

I'm solving HackerRank "Ransom Note" challenge. The code runs fine and cracks it, but I have an issue with its performance. It times out in some cases.

A kidnapper wrote a ransom note but is worried it will be traced back to him. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive and he must use whole words available in the magazine, meaning he cannot use substrings or concatenation to create the words he needs.

Given the words in the magazine and the words in the ransom note, print Yes if he can replicate his ransom note exactly using whole words from the magazine; otherwise, print No.

Input Format

The first line contains two space-separated integers describing the respective values of (the number of words in the magazine) and (the number of words in the ransom note).

The second line contains space-separated strings denoting the words present in the magazine.

The third line contains space-separated strings denoting the words present in the ransom note.

My implementation:

def ransom_note(magazine, ransom):
 for word in ransom:
 if word in magazine:
 magazine.remove(word)
 else:
 return False
 return True
m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
answer = ransom_note(magazine, ransom)
if(answer):
 print("Yes")
else:
 print("No")

It's timing out when there are too many items (30.000) on magazine or ransom. Performance talking, what can I improve here?

Answer 1

Your loop has a potential complexity of R * M (R number of words in ransom, M number of words in magazine). Additionally you use remove in the inner loop which which does linear search in magazine.

The solution is to count occurences of words in both, magazine and ransom. this is done in a single sweep and of linear complexity R + M (dict get/set is average linear).

the moste dense and readable solution is

from collections import Counter
def ransom_note(magazine, ransom):
 ran = Counter(ransom)
 mag = Counter(magazine)
 return len(ran - mag) == 0

if you assume a very long magazine and a short ransom message you could go for an early break by counting the ransom first, then do a down count with magazine words. magazine could be a generator in that case reading from an arbitrary large file.

from collections import Counter
def ransom_note(magazine, ransom):
 ran = Counter(ransom)
 if not ran:
 return True # handle edge case
 for m in magazine:
 if m in ran:
 # we need this word
 if ran[m] > 1:
 ran[m] -= 1
 # still need more of that one
 else:
 # the last usage of this word
 ran.pop(m)
 if len(ran) == 0:
 # we found the last word of our ransom
 return True
 return False

Answer 2

If we consider length of a magazine, \$N\,ドル and length of ransom note, M, your current code checks each word in the ransom note, m, up to \$n\$ (# of words in the magazine) times. This results in \$O(N*M)\$.

Instead of searching through the entire magazine word list again and again, it's possible to hash each word in the magazine and store a count along with it. Then, when you want to check if a word is in the magazine, you can check the hash in \$O(1)\$ time for a result of \$O(N)\$ to construct the hash and \$O(M)\$ to check all m words, which is a final \$O(N+M)\$.

In Python, you can construct this word/count dictionary with a Counter:

from collections import Counter
def ransom_note(magazine, ransom):
 word_counts = Counter(magazine)
 for word in ransom:
 if word_counts[word] > 0:
 word_counts[word] -= 1
 else:
 return False
 return True