# How to efficiently remove duplicates from an array without using Set

Asked  7 Months ago    Answers:  5   Viewed   43 times

I was asked to write my own implementation to remove duplicated values in an array. Here is what I have created. But after tests with 1,000,000 elements it took very long time to finish. Is there something that I can do to improve my algorithm or any bugs to remove ?

I need to write my own implementation - not to use `Set`, `HashSet` etc. Or any other tools such as iterators. Simply an array to remove duplicates.

``````public static int[] removeDuplicates(int[] arr) {

int end = arr.length;

for (int i = 0; i < end; i++) {
for (int j = i + 1; j < end; j++) {
if (arr[i] == arr[j]) {
int shiftLeft = j;
for (int k = j+1; k < end; k++, shiftLeft++) {
arr[shiftLeft] = arr[k];
}
end--;
j--;
}
}
}

int[] whitelist = new int[end];
for(int i = 0; i < end; i++){
whitelist[i] = arr[i];
}
return whitelist;
}
``````

67

Since this question is still getting a lot of attention, I decided to answer it by copying this answer from Code Review.SE:

You're following the same philosophy as the bubble sort, which is very, very, very slow. Have you tried this?:

• Sort your unordered array with quicksort. Quicksort is much faster than bubble sort (I know, you are not sorting, but the algorithm you follow is almost the same as bubble sort to traverse the array).

• Then start removing duplicates (repeated values will be next to each other). In a `for` loop you could have two indices: `source` and `destination`. (On each loop you copy `source` to `destination` unless they are the same, and increment both by 1). Every time you find a duplicate you increment source (and don't perform the copy). @morgano

Tuesday, June 1, 2021

answered 7 Months ago
93

A primitive method would be:

``````var obj = {};

for ( var i=0, len=things.thing.length; i < len; i++ )
obj[things.thing[i]['place']] = things.thing[i];

things.thing = new Array();
for ( var key in obj )
things.thing.push(obj[key]);
``````
Tuesday, June 1, 2021

answered 7 Months ago
55

Arrays in Java store one of two things: either primitive values (`int`, `char`, ...) or references (a.k.a pointers).

So, `new Integer[10]` creates space for 10 `Integer` references only. It does not create 10 `Integer` objects (or even free space for 10 `Integer` objects).

Incidentally that's exactly the same way that fields, variables and method/constructor parameters work: they too only store primitive values or references.

Monday, June 14, 2021

answered 6 Months ago
53

Your first call to `Arrays.asList` is actually returning a `List<double[]>` - it's autoboxing the argument, because a `double[]` isn't a `T[]`... generics don't allow for primitive types as type arguments.

If you want to convert a `double[]` into a `List<Double>`, you either need to do it manually or use a third-party library to do it. For example:

``````public List<Double> toList(double[] doubles) {
List<Double> list = new ArrayList<>(doubles.length);
for (double x : doubles) {
}
return list;
}
``````

Note that unlike `Arrays.asList` any subsequent changes to the array will not be reflected in the list or vice versa - it's a copy, not a view.

Saturday, August 7, 2021

answered 4 Months ago
14
``````List<Type> list = ...
list.removeIf(item -> item.getId() == something);
``````

As the name suggests, `removeIf()` removes all elements if they satisfy the predicate.

Thursday, October 28, 2021

answered 1 Month ago