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
Mark :
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:\n\na = [0,0,1,1,1,2,2,3,4]\n\ncurrent = None\ncount = 0\n\nfor n in a:\n if n != current:\n a[count] = n\n count+=1\n current = n\n\na[:count] \n# [0, 1, 2, 3, 4]\n\n\nThis will be linear time and constant space.",
2020-05-17T06:24:08
Samwise :
This approach isn't at all time-efficient, but it meets your criteria for space:\n\n>>> a = [0,0,1,1,1,2,2,3,4]\n>>> while any(a.count(x) > 1 for x in a):\n... for x in a:\n... if a.count(x) > 1:\n... x = a.pop(x)\n... break\n...\n>>> a\n[0, 1, 2, 3, 4]\n\n\nThe generally recommended way of doing this is of course:\n\na = list(set(a))\n",
2020-05-17T05:21:30