I need to come up with an algorithm that iterates through an array and if any element appears m times, then the array needs to be modified so that it only appears min(2, m) times. For example, if A = [2, 2, 2, 3, 4, 4, 5, 5, 5] and m = 3, A = [2, 2, 3, 4, 4, 5, 5]. It is easy to do with extra space or nonlinear time but I want to know how to do it in O(n) time and space. The array is already sorted.
It is apparently a variant of the "remove all duplicates of a sorted array" problem, but the O(n) algo for that works because it finds all distinct elements and inserts them one by one. In the problem above, you can't do that because you need to check how many times the particular element occurred.
I've tried the following algorithm:
def variant2(arr, m): vacant = 1 for i in range(1, len(arr)): if not arr[i] == arr[vacant - 1]: if i - vacant + 1 == m: vacant += min(2, m) - 1 arr[vacant] = arr[i] vacant += 1 temp = arr[:vacant][:] return temp
but this doesn't work as the overwriting of the "vacant" index will cause an element that wasn't duplicated before to be duplicated. For example, A = [2, 2, 2, 3, 4, ...] with m = 3 will become A = [2, 2, 3, 3, 4....].