# [ACCEPTED]-Remove duplicates from array in linear time and without extra arrays-arrays

If the integers are limited 0 to n, you 20 can move through the array, placing numbers 19 by their indices. Every time you replace 18 a number, take the value that used to be 17 there and move it to where it should be. For 16 instance, let's say we have an array of 15 size 8:

```
-----------------
|3|6|3|4|5|1|7|7|
-----------------
S
```

Where S is our starting point, and 14 we'll use C to keep track of our "current" index 13 below. We start with index 0, and move 3 12 to the 3 index spot, where 4 is. Save 4 11 in a temp var.

```
-----------------
|X|6|3|3|5|1|7|7| Saved 4
-----------------
S C
```

We then put 4 in the index 10 4, saving what used to be there, 5.

```
-----------------
|X|6|3|3|4|1|7|7| Saved 5
-----------------
S C
```

Keep 9 going

```
-----------------
|X|6|3|3|4|5|7|7| Saved 1
-----------------
S C
-----------------
|X|1|3|3|4|5|7|7| Saved 6
-----------------
S C
-----------------
|X|1|3|3|4|5|6|7| Saved 7
-----------------
S C
```

When we try to replace 7, we see a 8 conflict, so we simply don't place it. We 7 then continue from the starting index S, increment 6 it by 1:

```
-----------------
|X|1|3|3|4|5|6|7|
-----------------
S
```

1 is fine here, 3 needs to move

```
-----------------
|X|1|X|3|4|5|6|7|
-----------------
S
```

But 5 3 is a duplicate, so we throw it away and 4 keep iterating through the rest of the array.

So 3 basically, we move each entry at most 1 2 time, and iterate through the entire array. That's 1 O(2n) = O(n)

Assume `int a[n]`

is an array of integers in the range 5 [0,n-1]. Note that this differs slightly 4 from the stated problem, but I make this 3 assumption to make clear how the algorithm 2 works. The algorithm can be patched up to 1 work for integers in the range [0,n].

```
for (int i=0; i<n; i++)
{
if (a[i] != i)
{
j = a[i];
k = a[j];
a[j] = j; // Swap a[j] and a[i]
a[i] = k;
}
}
for (int i=0; i<n; i++)
{
if (a[i] == i)
{
printf("%d\n", i);
}
}
```

```
void printRepeating(int arr[], int size)
{
int i;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++)
{
if(arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
printf(" %d ", abs(arr[i]));
}
}
```

0

Can you sort? Sort with Radix Sort - http://en.wikipedia.org/wiki/Radix_sort with 3 complexity O(arraySize) for given case and 2 then remove duplicates from sorted array 1 O(arraySize).

Walk through the array assign array[array[i]] = -array[array[i]]; if 3 not negative; if its already negative then 2 its duplicate, this will work since all 1 values are within 0 and n.

Extending @Joel Lee's code for completion.

```
#include <iostream>
void remove_duplicates(int *a, int size)
{
int i, j, k;
bool swap = true;
while(swap){
swap = false;
for (i=0; i<size; i++){
if(a[i] != i && a[i] != a[a[i]]){
j = a[i];
k = a[j];
a[i] = k;
a[j] = j;
swap = true;
}
}
}
}
int main()
{
int i;
//int array[8] = {3,6,3,4,5,1,7,7};
int array[8] = {7,4,6,3,5,4,6,2};
remove_duplicates(array, sizeof(array)/sizeof(int));
for (int i=0; i<8; i++)
if(array[i] == i)
std::cout << array[i] << " ";
return 0;
}
```

0

With ES6 I think this can be solved with 7 only a few lines reducing the array into 6 an object and then using object.keys to 5 get array without duplicates. This probably 4 takes more memory. I'm not sure.

I did it 3 like this:

```
var obj = array.reduce(function (acc, elem) {
acc[elem] = true;
return acc;
},{});
var uniqueArray = Object.keys(obj);
```

This has the added bonus (or disadvantage) of 2 sorting the array. It works with strings 1 too.

Use the array a a container with negative 2 sign as an indicator, this will corrupt 1 the input though.

More Related questions

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.