Imagine you want to find all the duplicates in an array, and you must do this in O(1) space and O(N) time.
An algorithm like this would have O(N) space:
def find_duplicates(arr):
seen = set()
res = []
for i in arr:
if i in seen: res.append(i)
seen.add(i)
return res
My question is would the following algorithm use O(1) space or O(N) space:
def find_duplicates(arr):
seen = set()
res = []
while arr:
i = arr.pop()
if i in seen: res.append(i)
seen.add(i)
return res
Technically arr gets smaller and the sum of |seen| and |arr| will always be less than the original |arr|, but at the end of the day I think it's still allocating |arr| space for seen.
In order to determine the space complexity, you have to know something about how pop is implemented, as well as how Python manages memory. In order for your algorithm to use constant space, arr would have to release the memory used by popped items, and seen would have to be able to reuse that memory. However, most implementations of Python probably do not support that level of sharing. In particular, pop isn't going to release any memory; it will keep it against the possibility of needing it in the future, rather than having to ask to get the memory back.