Remove duplicates from unsorted array

Question

My method for quickly returning an array of non-duplicates from a given unsorted array only seems to work some of the time:

    public static int[] removeDuplicates(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }

    int lastFound = arr[0];

    int currPos = 1;
    for (int i = 1; i < arr.length; ++i) {
        int num = arr[i];
        if (lastFound != num) {
            lastFound = num;
            arr[currPos++] = num;
        }
    }

    return Arrays.copyOf(arr, currPos);
}

When I input:

int[] arr = {0, 1, 1, 0, 1, 1, 2, 2}
int[] arr2 = removeDuplicates(arr);

it will return:

arr2 = {0, 1, 0, 1, 2}

Where it should return (with no duplicates):

arr2 = {0, 1, 2}

Your algorithm is incorrect. For each element of the *input* array you have to check all elements of the *output* array whether the value is already among them; if not, add to the output array. (It doesn't matter if the output array reuses the input array.) — laune, Oct 25 '15 at 21:27

Andy Turner · Accepted Answer · 2015-10-25T21:44:42.960

3

In order to determine whether to add a value, you are only looking at the previous element (or, rather, the first element in the previous run of equal values).

This means that it will only work if all elements with a given value are contiguous in the array, which they aren't for your example input.

e.g. it would work for

{0, 0, 1, 1, 2}  // Sorted.

or

{2, 0, 0, 1, 1}  // Unsorted, but all equal elements are together.

In order to make it work, you need to record all elements that you've seen before, not just the one at the start of the previous run, e.g. by storing the seen elements in a Set. However, given that adding an already-present element to a set doesn't change the set, you may as well just add the whole array to the set:

LinkedHashSet<Integer> set = new LinkedHashSet<>(Arrays.asList(arr));

or

set.addAll(Arrays.asList(arr)); // If the set already exists.

If you want to return an int[] (as opposed to Integer[], which you could get using set.toArray(new Integer[])) you'd need to copy the elements back into an array:

int[] result = new int[set.size()];
int idx = 0;
for (int value : set) {
  result[idx++] = value;
}
return result;

edited Oct 25 '15 at 21:44

answered Oct 25 '15 at 21:27

Andy Turner

137,514
11
162
243

is it possible to do it in O(n) time and O(1) space ? if yes, how? – AnV Jul 30 '18 at 20:15
@AnV you can't resize an existing array, which makes it somewhat hard to do this completely in place. You can rearrange the array elements in place, and then create a new array at the end; but that would be inefficient time-wise. It's a trade-off. – Andy Turner Jul 30 '18 at 20:20
is it possible to rearrange the array elements "in place" in O(n) time? I mean if original arr is [2,1,3,2,1,4] can we re-arrange it to [2,1,3,4,1,4] and say size is 4. – AnV Jul 30 '18 at 20:27
@AnV no. Padding comment to minimum length. – Andy Turner Jul 30 '18 at 20:28

score 2 · Answer 2 · edited Dec 15 '15 at 04:22

the way to deal with the problem is record each element which appears in the array when iterating through the array,and delete duplicates of the element. Recording the element is using hashtable.

 public int[] removeDups(int[] data){
       Hashtable table = new Hashtable();
       ArrayList<int> arrayList= new ArrayList<int>(Arrays.asList(array));
       for(int i = 0; i < data.length; i++){
           if(table.containsKey(arrayList.get(i)){
          arrayList.remove(i);
      }else{
          table.put(arrayList.get(i),true);
      }
  }
  return arrayList.toArray();

}

This way, removing duplicates is easier.

Alex Rashkov · Answer 3 · 2015-10-25T21:49:31.857

You can use a set of Integers and that will make sure you have only unique values

HashSet<Integer> set = new HashSet<Integer>();
for (int i = 1; i < arr.length; ++i) {
    set.add(arr[i]);
}
return set.toArray();

Your approach will work with sorted array so if you use Merge sort to sort the elements in the array which will take O(n log n) worst case you can walk the array and exclude any item that is the same as the previous one in the array thus resulting in an array with only unique numbers.

public int[] removeDuplicates(int[] data) {
    // Make sure you have elemens in the array and it's not empty
    Arrays.sort(data);
    int number = data[0];
    ArrayList<Integer> result = new ArrayList<Integer>;
    for (int i = 1; i < data.length; ++i) {
        if (data[i] != number) {
            number = data[i];
            result.add(data[i]);
        }
    }

    result.toArray();
}

Remove duplicates from unsorted array

3 Answers3