I am trying to solve the "Ransom Note" problem on hackerank. Why isn't my code getting submitted? What can I do differently? is my total time complexity, in this case, it is O(n^2)?


import math
import os
import random
import re
import sys

# Complete the checkMagazine function below.
def checkMagazine(magazine, note):
    for word in note:                                         # O(n)
        if word not in magazine:                              # O(n)
            return 'No'
            magazine.remove(word)                             # O(n)

    return 'Yes'

if __name__ == '__main__':
    mn = input().split()

    m = int(mn[0])

    n = int(mn[1])

    magazine = input().rstrip().split()

    note = input().rstrip().split()

    print(checkMagazine(magazine, note))
  • 1
    \$\begingroup\$ "Why isn't my code getting submitted?" - I guess because you're not submitting it? \$\endgroup\$ – superb rain Sep 11 '20 at 17:24
  • \$\begingroup\$ And if you do submit it, it doesn't get accepted. Probably that's what you meant? Then you know that it's not correct, making this off-topic here. \$\endgroup\$ – superb rain Sep 11 '20 at 17:33
  • \$\begingroup\$ In your assessment of asymptotic bounds of complexity, you need more variables to model problem size. \$\endgroup\$ – greybeard Sep 13 '20 at 15:27
  • \$\begingroup\$ (You may try and find an approach minimising memory required.) \$\endgroup\$ – greybeard Sep 13 '20 at 15:29

You can find some ideas in the discussions tab of the original question: https://www.hackerrank.com/challenges/ctci-ransom-note/forum?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps.

To answer your quesitons: yes, your solution has time complexity of O(n^2).

The optinal solution should have time complexity of O(n):

  1. Go through magazine in O(n), get a map from words to counts.
  2. Go through note in O(n), also get a map from words to counts.
  3. Go through the map in step 2 in O(n), check for each word, whether the count of the map in step 1 is larger or not. Return True only when all the counts are no larger.

Not the answer you're looking for? Browse other questions tagged or ask your own question.