Search code examples
arrayslanguage-agnostic

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
Solution

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