CODEWITHSUNDEEP
pythontime-complexityhashset
Alex
Alex

Reputation: 39

What is the difference between hashSet.add(n) and myList.append(n) in terms of Time Complexity?

Starting to leetcode and get Time Exceed Limit error.

Here is the function:

def containsDuplicate(nums: list[int]) -> bool:
    tempset = []
    for n in nums:
        if n in tempset:
            return True
        else:
            tempset.append(n)
    return False

When I just use an array(list), it gives the error. If tempset is a set(), it does not. What is the difference between time complexities of the two operations? Shouldnt they both run in constant time? Or the problem is with n in tempset and how it calculates it behind the scene?

Upvotes: 0

Views: 68

Answers (1)

Urjit Desai
Urjit Desai

Reputation: 23

The issue here is with the line- if n in tempset:

When tempset is a list, the above line of code takes O(n) to execute as it iterates over each index to perform the check.

When tempset is a set, the above line of code takes O(1) to execute. Sets are implemented as hash tables, and they use a hash function to quickly locate the element in the set, making membership tests very efficient.

Upvotes: 0

Related Questions