0
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.

Nitin
  • 1
  • Need to know more about `storing_list.append(i)` – chux - Reinstate Monica Dec 23 '21 at 16:24
  • An `if` statement takes the time it takes to evaluate the condition. `i in storing_list` takes the time it takes to find `i`, which depends on the length of `storing_list` – rici Dec 23 '21 at 16:28
  • Hint: use a set, not a list. – rici Dec 23 '21 at 16:29
  • You need to consider the complexity of the individual operations you use. In particular, `in` and `append`. It is more than dubious that they are performed in constant time. –  Dec 23 '21 at 16:58

2 Answers2

0

As mentioned in the other topic Complexity of in operator in Python, 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
YuanPJ
  • 51
  • 4
0

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.

rici
  • 234,347
  • 28
  • 237
  • 341
  • Technically, early exit does not change the worst-case complexity. –  Dec 23 '21 at 17:01
  • @yves: that's obviously true, and I did say "**could be** a massive waste" for exactly that reason. However, in contexts other than the academic, this sort of inefficiency is going fail code reviews. – rici Dec 23 '21 at 22:11
  • That reminds me of the case of dichotomic search in a sorted array. Many implementations do test for equality of the key on every iteration and perform early exit. Though this is an "obvious" improvement, in fact it slows down the algorithm. –  Dec 24 '21 at 07:19
  • @yves: that's completely different, although it is an interesting case. But here I'm not suggesting a new test; the test is already being. The difference is what you do when the test fires: increment a count, or break/return. A more similar case is one of my bugbears in code reviews: using `if index(target, prefix) == 0` instead of `if startswith(target, prefix)` (substitute method names appropriate for your language). I got something like a 20% speedup for a single line CL from that one, once. On the service as a whole, not a microbenchmark. These things matter. – rici Dec 24 '21 at 07:39
  • Are you really explaining this to me ? –  Dec 24 '21 at 07:44
  • 1
    I don't know. Maybe I'm just counter-trolling. :-) – rici Dec 24 '21 at 07:49