Remove elements that appear m times 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....].
I don't really understand your problem, so here is how you can solve a similar problem: instead of removing duplicated, we want each element to appear at most twice. In other words, if an element appears in a run of length $\ell$, we replace it with a run of length $\min(\ell,2)$. Suppose that the array is $A_1,\ldots,A_n$.


Assign $\mathrm{curr} \gets A_1$. This variable will store the value being repeated in the current run.
Assign $\ell \gets 1$. This is the length of the current run.
Assign $\nu \gets 1$. This is the length of the "new" array.
Loop over the values $2 \leq i \leq n$:


If $A_i = \mathrm{curr}$, increase $\ell$ by 1.
If $A_i \neq \mathrm{curr}$, let $\mathrm{curr} \gets A_i$, and set $\ell \gets 1$.
If $\ell \leq 2$, insert the new element: increase $\nu$ by 1, and assign $A_\nu \gets \mathrm{curr}$.

Return $A_1,\ldots,A_\nu$.


You can prove by induction that $\nu \leq i$, and so information is erased only after it is read.

A more challenging task is: "If an element appears in a run of length $\ell \geq m$, replace it with a run of length $2$". In other words, we replace a run of length $\ell$ with a run of length $2$ whenever $\ell \geq m$ (assuming $m \geq 2$). We can accomplish this using a similar strategy:


Assign $\mathrm{curr} \gets A_1$. This variable will store the value being repeated in the current run.
Assign $\ell \gets 1$. This is the length of the current run.
Assign $\nu \gets 1$. This is the length of the "new" array.
Loop over the values $2 \leq i \leq n$:


If $A_i = \mathrm{curr}$, increase $\ell$ by 1.
If $A_i \neq \mathrm{curr}$, let $\mathrm{curr} \gets A_i$, and set $\ell \gets 1$.
If $\ell &lt; m$, insert the new element: increase $\nu$ by 1, and assign $A_\nu \gets \mathrm{curr}$.
If $\ell = m$, remove $m-2$ occurrences of $\mathrm{curr}$: decrease $\nu$ by $m-2$.

Return $A_1,\ldots,A_\nu$.