remove duplicates in a sorted array if duplicates are allowed at most twice

Question

Given a sorted array, remove the duplicates in place such that each element appear at most twice and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

The following is my code:

int rightMost_of_curElem(int A[], int curElem, int ind, int n)
{
    while(ind<n)
    {
        if(A[ind]!=curElem)
            break;
        ++ind;
    }

    return --ind;
}

int remove_duplicates(int A[], int n)
{
    int i=0;
    int unique_num = 0;
    while(i<n)
    {
        int cur_elem = A[i];
        int pos = rightMost_of_curElem(A, cur_elem, i, n);

        if(A[pos]==A[pos-1])
        {
            A[unique_num++] = A[pos];
        }
        A[unique_num++] = A[pos];

        i = pos+1;
    }

    return unique_num;
}

Answer 1

Opps one bug:

 if(A[pos]==A[pos-1])

If pos == 0 (if there is only one first element) it will fail (undefined behavior).

Two Recommendation:

This:

 int i=0;
 while(i<n)
 {
     // Stuff
     i = pos+1;
 }

Seems like a classic for(;;) loop.

 for(int i = 0; i < n; i = pos +1)
 {
 }

Don't use single letter variable names.
If your function is only slightly larger then looking through the code and finding all the uses of i can be hard. Give it a longer more unique name.

---

So the rest is just some personal preferences. Nothing I could complain about in a code review.

int rightMost_of_curElem(int A[], int curElem, int ind, int n)

This returns the righmost element. Which means the user has basically has the index to beginning an end of a range. Most C/C++ like functions use a concept of beginning to one past the end. So I would have made this return the index of the first element that did not match (and re-named slightly).

Slight improvement is that you pass the index of the current index which you already know equals the value. You should pass current index + 1 (avoids one compare).

int remove_duplicates(int A[], int n)

You hard code the number of elements to retain. In an interview (and in real life) I would have parametrized this.

Using if(A[pos]==A[pos-1]) as a test seems a bit hard to read when testing one or two elements. I would just use the distance between pos and i to find the number.

I would have written like this:

int getNextElement(int* data, int size, int index, int curElem)
{
    for( ; ((index < size) && (data[index] == curElem)) ; ++index)
    { /* No Body */ }

    return index;
}

int removeDuplicates(int* data, int size, int maxElements)
{
    int count = 0;
    int pos   = 0;
    for(int loop = 0; loop < size; loop = pos)
    {
        int pos = getNextElement(data, size, loop + 1, data[loop]);

        int lastElement = min(loop + maxElement, pos);
        memcpy(data + count, data + loop, (lastElement - loop) * sizeof(int));
        count += (lastElement - loop)
        /*
        for(int copy = loop; copy < lastElements; ++copy, ++count)
        {
            data[count] = data[copy];
        }
        */
    }

    return count;
}

int removeDuplicates2(int* data, int size) {return removeDuplicates(data, size, 2);}

Answer 2

General comments

• mixed naming style - youve got camelCase and separate_words combined!

• upper case naming (A[])is for #define constants

• I prefer to see a space after while and if etc and spaces around operators (!= etc)

---

In rightMost_of_curElem

• verbose name

• function takes 4 parameters which seems excessive; strspn does the same for strings and takes just 2.

• A[] should be const

• returns -1 if ind and n are both 0. Ok that is not going to happen but a function that has input conditions under which it fails is undesirable.

• should be static

• pedantic: missing braces on the if statement

---

In remove_dupicates

unique_num is an odd name

• cur_elem is unnecessary - and why is it cur_elem here and curElem in rightMost_of_curElem (name and parameter)

• pos, i and unique_num here and ind in rightMost_of_curElem are the same quatity. One wouldn't guess this from the names. You can't always use the same name everywhere, but one might at least expect ind and pos to be the same.

• as @LokiAstari says, there is a bug in your if(A[pos]==A[pos-1]). You must always be careful when using negative offsets in array indices.

---

Here's another approach, for what it is worth:

static inline int intspan(const int *in, const int *end)
{
    int span = 1;
    for (; in + span < end; ++span) {
        if (in[0] != in[span]) {
            break;
        }
    }
    return span;
}

static size_t remove_duplicates(int *const in, int n)
{
    const int *data = in;
    const int *end = data + n;
    int *out = in;

    while (data < end) {
        int span = intspan(data, end);
        *out++ = *data;
        if (span > 1) {
            *out++ = *data;
        }
        data += span;
    }
    return (size_t) (out - in);
}