szhongren - 9 months ago 32

Python Question

`def firstMissingPositive(self, A):`

least = 1024*1024*1024

# worst case n ops

for i in A:

if i < least and i > 0:

least = i

if least > 1:

return 1

else:

# should be O(n)

A_set = set(A)

# worst case n ops again

while True:

least += 1

if least not in A_set:

return least

I only ask because it seemed too simple for the given problem, which most people here may have seen on Leetcode or someplace similar. Is there something I'm not aware of in Python's implementation of set or dict? Lookup should be O(1) and converting a list to a set should be O(n) from what I understand.

Answer

It's `O(n)`

space since you need to build the set.

As for the time, according to the Python wiki, set containment takes `O(n)`

worst case. So your algorithm is thus `O(n^2)`

. Note this is worst case - the average time for set containment is `O(1)`

and so the average time complexity for your algorithm is indeed `O(n)`

.

You can get the worst-case down to `O(n log n)`

by using an ordered set, but then the average-time will be `O(n log n)`

as well.

Source (Stackoverflow)