HackerRank Ransom Note challenge 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?
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] &gt; 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