class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        storing_list = []
        counter = 0
        for i in nums:
            if i in storing_list:
                counter  = 1
            else:
                storing_list.append(i)
        if counter > 0:
            return True
        else:
            return False

This should run in O(n) time right? Leetcode is saying that time limit is exceeded, which means it runs too slow. I am confused on what the run time of this algorithm is.

CodePudding user response：

As mentioned in the other topic enter link description here, the complexity of in of list is O(n), so the overall complexity is O(n^2) because you iterate over nums and call in in the for-loop.

If you want an O(n) solution, you can use set instead of list, because in of set has average O(1) complexity. For example,

storing_set = {set}
counter = 0
for i in nums:
    if i in storing_set:
        counter  = 1
    else:
        storing_set.add(i)
    if counter > 0:
        return True
    else:
        return False

CodePudding user response：

An if statement takes the time it takes to evaluate the condition.

In this case, the condition is i in storing_list, which requires an element-by-element search of storing_list. In particular, if i is not in the list, the search will take time linear in the nber of elements seen so far, so calling it n times on a list of items without duplicates will take quadratic time. Not good.

You would be a lot better off using a set, which can do a lookup in constant time, on average.

Note that counting the number of duplicates and then returning True if the count is greater than one could be a massive waste of time. Suppose the list consists of two identical values followed by 10 million unique values. You could just reurn True as soon as you see the second element, no? The count is never going to go down. Handling the other ten million values is totally pointless.