HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

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

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
twiceallowedmostarearrayremovesortedduplicates

Problem

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;
}

Solution

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);}

Code Snippets

if(A[pos]==A[pos-1])
int i=0;
 while(i<n)
 {
     // Stuff
     i = pos+1;
 }
for(int i = 0; i < n; i = pos +1)
 {
 }
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);}

Context

StackExchange Code Review Q#23582, answer score: 5

Revisions (0)

No revisions yet.