Removing duplicates from an array in C/C++ in O(n) time

Question

Suppose i have an array like

int array[] = {1,1,1,4,5,7,7,9,11};

I should be able to remove all the duplicates and hence my output should be {1,4,5,7,9,11}.

Constraints:

I am not allowed to use any kind of extra memory apart from variables
I should be able to resize the array
I am not allowed to use containers like Hashset or set etc:
Should be done in O(n) time

Is this homework? And is the input sorted? And what have you tried? — Dietrich Epp, Oct 07 '11 at 22:43
Did you check this : http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array — FailedDev, Oct 07 '11 at 22:44
BTW...It is important to the solution that the input is sorted. This is one of these questions where the solution is obvious once you know it, *and* is the same as you would use in doing it by hand. — dmckee --- ex-moderator kitten, Oct 07 '11 at 22:45
@dmckee: Technically, the input need not be sorted since the elements have a fixed size, so a radix or bucket sort will take `O(N)`. But this is esoteric. — Dietrich Epp, Oct 07 '11 at 22:57
You can't resize an array like `int array[] = {1,1,1,4,5,7,7,9,11};`, so blob 2 is out. — Steve Jessop, Oct 07 '11 at 23:06
@Dietrich You're right, of course. Not only that but, you would also be OK with an unsorted array in which you could guarantee that all like elements are together. But again, that's a odd case. — dmckee --- ex-moderator kitten, Oct 07 '11 at 23:21
@DietrichEpp this question was asked to me during interview for amazon — jerry, Oct 08 '11 at 03:50
@SteveJessop you r right. By resizing i meant that we are supposed to put something like '\0' after rearranging the elements, and print the array until null is found. — jerry, Oct 08 '11 at 03:59

score 2 · Answer 1 · answered Oct 07 '11 at 22:51

2

If the array is sorted, then this logic could be applied.

Have two pointers(P1,P2) pointing to the beginning of the array.
Increment pointer P2. Check if the value pointed by P2 and P1 are equal.
If yes, increment further and reach to the point where P1 and P2 pointed values are not equal. Now go to step 5.
If no, assign P1 to P2 and repeat from step 2.
Now, remove the elements between P1 and P2. Assign P2 to P1.

Repeat the process until you reach the end point of the array.

answered Oct 07 '11 at 22:51

Mahesh

34,573
20
89
115

how can you remove elements from an array like that ?? – jerry Oct 08 '11 at 04:02
Array **cannot** be resized. But in your question, you mentioned it is resizable. – Mahesh Oct 08 '11 at 04:03
Sorry i did not specify it clearly. By resizing i meant that we are supposed to put something like '\0' after rearranging the elements, and print the array until null is found – jerry Oct 08 '11 at 05:13

ggupta1612 · Answer 2 · 2011-10-07T23:08:02.937

Traverse the array and compare each element with the previous element. If its the same, you know its a duplicate. Keep another pointer that copies each unique element within the array. Eg. 1,1,4,5,7,7,9,11

Keep two pointers i and j at starting of array i.e. 1.
Use i to traverse the array and j to keep track of the unique element. Initially, 1 is unique so copy a[i] to a[j] and increment both.
Next 1 is duplicate, so only increment j.
When 4 encountered, its unique, so copy a[i] to a[j] (j points to the second i.e. the duplicate 1) and increment both.
Do the same till i fully traverses the array.
a[0...j] gives all unique elements.

Complexity: O(n)

score 0 · Answer 3 · answered Oct 07 '11 at 22:57

0

If you know a maximum value (MAX_INT_VALUE) for the ints and aren't worried about memory constraints, this is a somewhat creative solution that got me through a job interview:

public int* removeDuplicates(int* array, int arraySize) {

    short indexMarkers [MAX_INT_VALUE];
    int i = 0;
    for (i=0; i<arraySize;i++) {
        indexMarkers[array[i]]++;
    }

    int cursor = 0;
    for(i=0; i<MAX_INT_VALUE;i++) {
        if (indexMarkers[i] > 0) {
            array[cursor] = i;
            cursor++;
        }
    }

    //resize array to be sizeof(int)*cursor

    return array;
}

The idea is to have the values of the items in the array be the indices of the indexMarkers array. Then you're just checking whether the value existed at all to output the new array. This would be at least O(2N) though.

answered Oct 07 '11 at 22:57

John Leehey

22,052
8
61
88

Full points for creativity, but there are 2 problems with this: 1) One of the requirements was that you could not allocate extra memory. 2) This requires 2 passes over the array, while the trivial solution (assuming the array is sorted) requires only 1 pass over the array. – riwalk Oct 07 '11 at 23:08
Thanks steve. meh it was closed anyway. – John Leehey Oct 07 '11 at 23:09
1

@Stargazer712 I never said it was faster. But you're right I didn't heed the extra memory constraint. This way will work even if the array is not sorted as well. – John Leehey Oct 07 '11 at 23:11

Removing duplicates from an array in C/C++ in O(n) time

3 Answers3

Linked