Delete duplicates from sorted array (6.5) variant

#1

I am struggling with the 2nd variant for 6.5 (EPI Java):

Write a program which takes as input a sorted array A of integers and a positive integer m, and updates A so that if x appears m times in A it appears exactly min(2,m) times in A.

I have adapted the original solution to keep track of the number of times an integer is repeated and I am trying to use this value to adjust writeIndex before writing the next non-repeated integer, but unable to figure it out.

Can someone please provide a hint?

Thanks.

0 Likes
#2

Hi @ripuhan,

The hint I think is to having more variable(s) to store not only previous but also the one before previous elements. With that, you shall be able to adapt the original solution for this.

0 Likes
#3

How I feel seeing unanswered variant questions on this forum: https://xkcd.com/979/

Here’s my Javascript solution. Best wishes, future readers!

function removeDuplicates2(arr, m) {
  const min = Math.min(2, m);

  let vacancy = 0;
  let lastUniqueNum = null;
  let dupes = 0;

  for(let i = 0; i < arr.length; i++) {
    if(arr[i] !== lastUniqueNum) {
      if(dupes === m) {
        vacancy -= dupes - min;
      }
      lastUniqueNum = arr[i];
      dupes = 0;
    }

    dupes++;
    arr[vacancy++] = arr[i];
  }

  return vacancy;
}
0 Likes
#4

This seems to work for me and it is written in python:

def delete_duplicates_min(A, m):
    if not A or m <= 0:
        return 0
    write_index = 1
    count = 1
    for i in range(1, len(A)):
        if A[write_index - 1] == A[i]:
            count += 1
        else:
            count = 1
        if A[write_index - 1] != A[i] or count <= min(2, m):
            A[write_index] = A[i]
            write_index += 1
    return write_index
0 Likes