Python HashTable implementation quicker than list iteration?

Question

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

I thought of that as well. This change passes more tests, but still not all of them. Any thoughts as to why the other implementation is quicker? — Michael Cavallaro
– Michael Cavallaro, Commented May 15, 2018 at 12:35
count is linear, so your code has quadratic complexity. By putting it in a dict first, it only needs O(1) to get the count for a certain letter. — tobias_k
– tobias_k, Commented May 15, 2018 at 12:37
Hash table iteration is not necessarily faster but hash table lookup is O(1) whereas each call to list.count() is O(n). — zwer
– zwer, Commented May 15, 2018 at 12:39

FHTMitchell · Accepted Answer · 2018-05-15 12:40:11Z

1

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

answered May 15, 2018 at 12:40

FHTMitchell

12.2k2 gold badges40 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

tobias_k · Accepted Answer · 2018-05-15 12:42:10Z

1

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"

answered May 15, 2018 at 12:42

tobias_k

83.1k12 gold badges130 silver badges186 bronze badges

Collectives™ on Stack Overflow

Python HashTable implementation quicker than list iteration?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related