Let's say we need to find all the elements occurring an odd number of times in a sorted list in O(N) time and O(1) space complexity.
ls = [1,2,2,3,3,3,4,5,5,6,6,6,6,6]
output = [1,3,4,6]
We are not going to return a new list, perhaps will be overwrite the existing one
I have an approach which uses a hashing technique, but it results in O(N) space complexity.
I have tried bitwise manipulation using XOR, but I am not able to solve the question.
Iterate through the list, counting cases where the present item is the same as the previous one, and overwriting towards the start of the list when it is different and the count is an odd number.
This solution overwrites the existing list rather than allocating a new one, and has O(N) time complexity. Because the new list will be shorter, we have to pop the remaining items from the end of it. (We would normally splice using ls = ls[position:] but that would assign a new list, which isn't allowed.)
def keep_odd_elements(ls):
count = 0
write_position = 0
previous = object()
for item in ls:
if item == previous:
count += 1
else:
# Write the odd-counted numbers towards the start of the list
if count % 2:
ls[write_position] = previous
write_position += 1
count = 1
previous = item
if count % 2:
ls[write_position] = previous
write_position += 1
# Remove the leftover items at the end of the list
for _ in range(write_position, len(ls)):
ls.pop()
ls = [1,2,2,3,3,3,4,5,5,6,6,6,6,6]
keep_odd_elements(ls)
print(ls) # [1, 3, 4, 6]
If we remove the requirement not to allocate a new list, then we can write this much more elegantly:
def get_odd_elements(ls):
count = 0
for a, b in zip([object()] + ls, ls + [object()]):
if a == b:
count += 1
else:
if count % 2:
yield a
count = 1
print(list(get_odd_elements([1,2,2,3,3,3,4,5,5,6,6,6,6,6])))