CODEWITHSUNDEEP
pythonpython-3.xbig-o
Michael Cavallaro
Michael Cavallaro

Reputation: 48

Python HashTable implementation quicker than list iteration?

This is a problem from HackerRank. My implementation as shown below passes most of the test but for the tests that it fails, it states that it is taken too long. After looking at other submissions, I found that another user's implementation (credit to saikiran9194) passes all tests almost immediately. I really am having trouble understanding why his solution is the most efficient at scale.

My Implementation:

m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
yesNo = "Yes"
for i in ransom:
    if(ransom.count(i) > magazine.count(i)):
        yesNo = "No"
print(yesNo)

More Time Efficient Implementation

def ransom_note(magazine, ransom):
    rc = {} # dict of word: count of that word in the note
    for word in ransom:
        if word not in rc:
            rc[word] = 0
        rc[word] += 1

    for word in magazine:
        if word in rc:
            rc[word] -= 1
            if rc[word] == 0:
                del rc[word]
                if not rc:
                    return True
    return False

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")

Upvotes: 0

Views: 83

Answers (2)

tobias_k
tobias_k

Reputation: 82929

list.count has linear complexity, so your code has quadratic complexity overall, doing linear work in each iteration of the loop. By putting the lists in a dict first, it only needs O(1) to get the count for a certain letter.

You can just wrap those lists into collections.Counter (not tested):

m, n = map(int, input().strip().split())
magazine = Counter(input().strip().split())
ransom = Counter(input().strip().split())
yesNo = "Yes"
for i in ransom:
    if(ransom[i] > magazine[i]):
        yesNo = "No"
print(yesNo)

Or shorter using any

yesno = "No" if any(random[i] > magazine[i] for i in ransom) else "Yes"

Upvotes: 1

FHTMitchell
FHTMitchell

Reputation: 12156

It's the difference between list.count and dict.__getitem__ (rc[word]). list.count is O(n) whereas dict.__getitem__ is O(1) due to, as you mention, hashing.

Source: https://wiki.python.org/moin/TimeComplexity

Upvotes: 1

Related Questions