CODEWITHSUNDEEP
arrayslanguage-agnostic
Kumar Mangalam
Kumar Mangalam

Reputation: 777

How can I remove duplicates from array without using another array?

I have found this question in a interview

I have array

a = [0,0,1,1,1,2,2,3,4]

I have a sorted array and I want to remove the duplicates from the given array without using any other array, i.e. space complexity should be O(1). Output should be length of the array without duplicates.

Output,

a = [0,1,2,3,4]
length = 5

Upvotes: 1

Views: 1666

Answers (3)

Mark
Mark

Reputation: 92450

If you really want this in constant space, you need to be careful not to do anything that will reallocate a new array or a temp array. You can do this by simply overwriting the elements at the front of the array and keeping track of the count. At the end, the solution will be the front slice of the array from 0 to count:

a = [0,0,1,1,1,2,2,3,4]

current = None
count = 0

for n in a:
    if n != current:
        a[count] = n
        count+=1
        current = n

a[:count]  
# [0, 1, 2, 3, 4]

This will be linear time and constant space.

Upvotes: 4

Pavel Bogdanov
Pavel Bogdanov

Reputation: 47

def duplicate_remover(input_array):
    for item in input_array:
        while input_array.count(item) > 1:
            input_array.remove(item)
    return input_array

my_array = [0,0,0,0,0,1,1,2,2,2,3,3,3,4,5,6]
print(duplicate_remover(my_array))

Upvotes: 0

Samwise
Samwise

Reputation: 71507

This approach isn't at all time-efficient, but it meets your criteria for space:

>>> a = [0,0,1,1,1,2,2,3,4]
>>> while any(a.count(x) > 1 for x in a):
...     for x in a:
...         if a.count(x) > 1:
...             x = a.pop(x)
...             break
...
>>> a
[0, 1, 2, 3, 4]

The generally recommended way of doing this is of course:

a = list(set(a))

Upvotes: 0

Related Questions