1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't understand the goal. Suppose that the original array consists of element $a_i$ repeated $\ell_i$ times. How should the new array look? $\endgroup$ – Yuval Filmus Dec 30 '17 at 8:44
  • $\begingroup$ Also, I suspect that the phrase "$O(n)$ time and space" is missing a space complexity constraint, say "$O(1)$ space". $\endgroup$ – Yuval Filmus Dec 30 '17 at 9:20
  • $\begingroup$ I don't know how to format so bear with me. If element a_i is repeated l_i times, and l_i != m, then the output array should have the element a_i repeated l_i times as well in the order it was found. If l_i = m, then a_i should appear min(2, m) times in the output array. $\endgroup$ – Jeremy Fisher Dec 30 '17 at 22:09
  • $\begingroup$ Yes I mean constant space $\endgroup$ – Jeremy Fisher Dec 30 '17 at 22:25
1
$\begingroup$

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

  1. Assign $\mathrm{curr} \gets A_1$. This variable will store the value being repeated in the current run.
  2. Assign $\ell \gets 1$. This is the length of the current run.
  3. Assign $\nu \gets 1$. This is the length of the "new" array.
  4. 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}$.
  5. 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:

  1. Assign $\mathrm{curr} \gets A_1$. This variable will store the value being repeated in the current run.
  2. Assign $\ell \gets 1$. This is the length of the current run.
  3. Assign $\nu \gets 1$. This is the length of the "new" array.
  4. 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 < 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$.
  5. Return $A_1,\ldots,A_\nu$.
$\endgroup$
  • $\begingroup$ Sorry for the confusion, the OP was more similar to your 2nd implementation. As far as your first implementation goes, I think it would fail if you have A = [2, 2, 2, 3,..]. Here, curr would remain 2, and l would become 3 until i = 4 where it would be reset to 1, hence the output array would have A = [2, 2, 2, 3, ...], instead of 2 repeating 2 times. $\endgroup$ – Jeremy Fisher Dec 30 '17 at 22:24
  • $\begingroup$ I think the code is OK. Try running it. $\endgroup$ – Yuval Filmus Dec 30 '17 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.