I was asked this question in an interview. There is a sorted array with duplicates. The goal is to return the array with unique elements first and duplicates at the end preserving the order. For example
[1, 1, 2, 3, 4, 4, 5] should become
[1, 2, 3, 4, 5, 1, 4].
I was able to solve the question with an extra space (O(n) space) and linear time (O(n) time), but I am not sure if that is the best answer, ideally using no linear space.
I searched stackoverflow and found similar questions but not exactly the same. For example there was a question sorting an array and moving duplicates to the end, but in my case the array is already sorted and the goal is to only move duplicates to the end.
If your values are in limited range, there exists solution in O(n) time and O(1) space.
Determine the maximum value in array. Get some constant
C > arraymax, as example -
C = 10 for your array.
Scan array, squeezing unique values and counting duplicates for every value. If value
K>0 duplicates, write
V+C*K instead of value.
At the next scan find values with duplicates, extract number of duplicates and write them after squeezed unique values.
def dedup(lst): mx = max(lst) + 1 dupcnt = 0 delcnt = 0 start = 0 for i in range(1, len(lst) + 1): if i == len(lst) or (lst[i] != lst[start]): lst[start - delcnt] = lst[start] + dupcnt * mx delcnt += dupcnt start = i dupcnt = 0 else: dupcnt += 1 dupidx = len(lst) - delcnt for i in range(0, len(lst) - delcnt): dupcnt = lst[i] // mx if dupcnt: lst[i] %= mx for j in range(dupidx, dupidx+dupcnt): lst[j] = lst[i] dupidx += dupcnt return lst print(dedup([1,2,2,2,3,4,4,5])) >>> [1, 2, 3, 4, 5, 2, 2, 4]