szhongren szhongren - 1 month ago 4
Python Question

Is the below function O(n) time and O(1) space, where n = |A|?

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


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.