[java] How to efficiently remove duplicates from an array without using Set

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

This question is related to java arrays optimization

The answer is


Not a big fun of updating user input, however considering your constraints...

public int[] removeDup(int[] nums) {
  Arrays.sort(nums);
  int x = 0;
  for (int i = 0; i < nums.length; i++) {
    if (i == 0 || nums[i] != nums[i - 1]) {
    nums[x++] = nums[i];
    }
  }
  return Arrays.copyOf(nums, x);
}

Array sort can be easily replaced with any nlog(n) algorithm.


Just a trick to remove duplicates.

public class RemoveDuplicates {
    public static void main(String[] args) {
        int[] arr = {2,2,2,2,2,5,9, 4,5,6,1,6,6,2,4,7};
        arr = removeDuplicates(arr);    
        print(arr);
    }

    public static int[] removeDuplicates(int [] arr) {
        final int garbage = -2147483648;
        int duplicates = 0;

        for(int i=0; i<arr.length; i++) {
            for(int j=i+1; j<arr.length; j++) {
                if (arr[i] == arr[j]) {
                    arr[i] = garbage;
                    duplicates++;
                }
            }
        }

        int[] nArr = new int[arr.length - duplicates];
        int nItr = 0;
        for(int i=0; i<arr.length; i++) {
            if (arr[i] != garbage) {
                nArr[nItr] = arr[i];
                nItr++;
            } 
        }
        return nArr;
    }

    public static void print(int [] arr) {
        for (int n : arr) {
            System.out.print(n + "\t");
        }
    }

}

public static void main(String[] args) {
        Integer[] intArray = { 1, 1, 1, 2, 4, 2, 3, 5, 3, 6, 7, 3, 4, 5 };
        Integer[] finalArray = removeDuplicates(intArray);
        System.err.println(Arrays.asList(finalArray));
    }

    private static Integer[] removeDuplicates(Integer[] intArray) {
        int count = 0;
        Integer[] interimArray = new Integer[intArray.length];
        for (int i = 0; i < intArray.length; i++) {
            boolean exists = false;
            for (int j = 0; j < interimArray.length; j++) {
                if (interimArray[j]!=null && interimArray[j] == intArray[i]) {
                    exists = true;
                }
            }
            if (!exists) {
                interimArray[count] = intArray[i];
                count++;
            }
        }
        final Integer[] finalArray = new Integer[count];
        System.arraycopy(interimArray, 0, finalArray, 0, count);
        return finalArray;
    }

class Demo 
{
    public static void main(String[] args) 
    {
        int a[]={3,2,1,4,2,1};
        System.out.print("Before Sorting:");
        for (int i=0;i<a.length; i++ )
        {
            System.out.print(a[i]+"\t");
        }
        System.out.print ("\nAfter Sorting:");
        //sorting the elements
        for(int i=0;i<a.length;i++)
        {
            for(int j=i;j<a.length;j++)
            {
                if(a[i]>a[j])
                {
                    int temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }

            }
        }

        //After sorting
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]+"\t");
        }
        System.out.print("\nAfter removing duplicates:");
        int b=0;
        a[b]=a[0];
        for(int i=0;i<a.length;i++)
        {
            if (a[b]!=a[i])
            {
                b++;
                a[b]=a[i];
            }
        }
        for (int i=0;i<=b;i++ )
        {
            System.out.print(a[i]+"\t");
        }
    }
}
  OUTPUT:Before Sortng:3 2 1 4 2 1 After Sorting:1 1 2 2 3 4 
                Removing Duplicates:1 2 3 4

you can take the help of Set collection

int end = arr.length;
Set<Integer> set = new HashSet<Integer>();

for(int i = 0; i < end; i++){
  set.add(arr[i]);
}

now if you will iterate through this set, it will contain only unique values. Iterating code is like this :

Iterator it = set.iterator();
while(it.hasNext()) {
  System.out.println(it.next());
}

Okay, so you cannot use Set or other collections. One solution I don't see here so far is one based on the use of a Bloom filter, which essentially is an array of bits, so perhaps that passes your requirements.

The Bloom filter is a lovely and very handy technique, fast and space-efficient, that can be used to do a quick check of the existence of an element in a set without storing the set itself or the elements. It has a (typically small) false positive rate, but no false negative rate. In other words, for your question, if a Bloom filter tells you that an element hasn't been seen so far, you can be sure it hasn't. But if it says that an element has been seen, you actually need to check. This still saves a lot of time if there aren't too many duplicates in your list (for those, there is no looping to do, except in the small probability case of a false positive --you typically chose this rate based on how much space you are willing to give to the Bloom filter (rule of thumb: less than 10 bits per unique element for a false positive rate of 1%).

There are many implementations of Bloom filters, see e.g. here or here, so I won't repeat that in this answer. Let us just assume the api described in that last reference, in particular, the description of put(E e):

true if the Bloom filter's bits changed as a result of this operation. If the bits changed, this is definitely the first time object has been added to the filter. If the bits haven't changed, this might be the first time object has been added to the filter. (...)

An implementation using such a Bloom filter would then be:

public static int[] removeDuplicates(int[] arr) {
    ArrayList<Integer> out = new ArrayList<>();
    int n = arr.length;
    BloomFilter<Integer> bf = new BloomFilter<>(...);  // decide how many bits and how many hash functions to use (compromise between space and false positive rate)

    for (int e : arr) {
        boolean might_contain = !bf.put(e);
        boolean found = false;
        if (might_contain) {
            // check if false positive
            for (int u : out) {
                if (u == e) {
                    found = true;
                    break;
                }
            }
        }
        if (!found) {
            out.add(e);
        }
    }
    return out.stream().mapToInt(i -> i).toArray();
}

Obviously, if you can alter the incoming array in place, then there is no need for an ArrayList: at the end, when you know the actual number of unique elements, just arraycopy() those.


Heres a simpler, better way to do this using arraylists instead:

public static final <T> ArrayList<T> removeDuplicates(ArrayList<T> in){
    ArrayList<T> out = new ArrayList<T>();
    for(T t : in) 
        if(!out.contains(t)) 
            out.add(t);
    return out;
}

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

int end = arr.length;

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

//Remove duplicate from sorted array

public class RemDupFromArray {
    static int num;
    public static void main(String[] args){
        int arr[] = {0,0,2,2,3, 5, 5,7, 7, 7};
        for(int i=0;i<arr.length-1;i++){
            if(num!=arr[i]){
                num=arr[i];
                System.out.print(arr[i]);
            }
        }
    }
}

You can use an auxiliary array (temp) which in indexes are numbers of main array. So the time complexity will be liner and O(n). As we want to do it without using any library, we define another array (unique) to push non-duplicate elements:

_x000D_
_x000D_
var num = [2,4,9,4,1,2,24,12,4];_x000D_
let temp = [];_x000D_
let unique = [];_x000D_
let j = 0;_x000D_
for (let i = 0; i < num.length; i++){_x000D_
  if (temp[num[i]] !== 1){_x000D_
    temp[num[i]] = 1;_x000D_
    unique[j++] = num[i];_x000D_
  }_x000D_
}_x000D_
console.log(unique);
_x000D_
_x000D_
_x000D_


import java.util.*;
class removeDuplicate{
int [] y ;

public removeDuplicate(int[] array){
    y=array;


    for(int b=0;b<y.length;b++){
        int temp = y[b];
        for(int v=0;v<y.length;v++){
            if( b!=v && temp==y[v]){
                y[v]=0;
            }
        }
    }




}

This is not using Set, Map, List or any extra collection, only two arrays:

package arrays.duplicates;

import java.lang.reflect.Array;
import java.util.Arrays;

public class ArrayDuplicatesRemover<T> {

    public static <T> T[] removeDuplicates(T[] input, Class<T> clazz) {
        T[] output = (T[]) Array.newInstance(clazz, 0);
        for (T t : input) {
            if (!inArray(t, output)) {
                output = Arrays.copyOf(output, output.length + 1);
                output[output.length - 1] = t;
            }
        }
        return output;
    }

    private static <T> boolean inArray(T search, T[] array) {
        for (T element : array) {
            if (element.equals(search)) {
                return true;
            }
        }
        return false;
    }

}

And the main to test it

package arrays.duplicates;

import java.util.Arrays;

public class TestArrayDuplicates {

    public static void main(String[] args) {
        Integer[] array = {1, 1, 2, 2, 3, 3, 3, 3, 4};
        testArrayDuplicatesRemover(array);
    }

    private static void testArrayDuplicatesRemover(Integer[] array) {
        final Integer[] expectedResult = {1, 2, 3, 4};
        Integer[] arrayWithoutDuplicates = ArrayDuplicatesRemover.removeDuplicates(array, Integer.class);
        System.out.println("Array without duplicates is supposed to be: " + Arrays.toString(expectedResult));
        System.out.println("Array without duplicates currently is: " + Arrays.toString(arrayWithoutDuplicates));
        System.out.println("Is test passed ok?: " + (Arrays.equals(arrayWithoutDuplicates, expectedResult) ? "YES" : "NO"));
    }

}

And the output:

Array without duplicates is supposed to be: [1, 2, 3, 4]
Array without duplicates currently is: [1, 2, 3, 4]
Is test passed ok?: YES

public static int[] removeDuplicates(int[] arr){
    HashSet<Integer> set = new HashSet<>();
    final int len = arr.length;
    //changed end to len
    for(int i = 0; i < len; i++){
        set.add(arr[i]);
    }

    int[] whitelist = new int[set.size()];
    int i = 0;
    for (Iterator<Integer> it = set.iterator(); it.hasNext();) {
        whitelist[i++] = it.next();
    }
    return whitelist;
}

Runs in O(N) time instead of your O(N^3) time


The most efficient way to remove duplicates from integer array without using set is, just create a temp array and iterate the original array and check if number exists in temp array then do not push into array else put into temp array and return temp array as result. Please consider the following code snippet :

package com.numbers;

import java.util.Arrays;

public class RemoveDuplicates {
    public int[] removeDuplicate(int[] array) {
        int[] tempArray = new int[array.length];
        int j = 0;
        for (int i : array) {
            if (!isExists(tempArray, i)) {
                tempArray[j++] = i;
            }
        }
        return tempArray;
    }

    public static boolean isExists(int[] array, int num) {
        if (array == null)
            return false;
        for (int i : array) {
            if (i == num) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int [] array = { 10, 20, 30, 10, 45, 30 };
        RemoveDuplicates duplicates = new RemoveDuplicates();
        System.out.println("Before removing duplicates : " + Arrays.toString(array));
        int [] newArray = duplicates.removeDuplicate(array);
        System.out.println("After removing duplicates : " + Arrays.toString(newArray));

    }
}

public static void main(String args[]) {
    int[] intarray = {1,2,3,4,5,1,2,3,4,5,1,2,3,4,5};

    Set<Integer> set = new HashSet<Integer>();
    for(int i : intarray) {
        set.add(i);
    }

    Iterator<Integer> setitr = set.iterator();
    for(int pos=0; pos < intarray.length; pos ++) {
        if(pos < set.size()) {
            intarray[pos] =setitr.next();
        } else {
            intarray[pos]= 0;
        }
    }

    for(int i: intarray)
    System.out.println(i);
}

I know this is kinda dead but I just wrote this for my own use. It's more or less the same as adding to a hashset and then pulling all the elements out of it. It should run in O(nlogn) worst case.

    public static int[] removeDuplicates(int[] numbers) {
    Entry[] entries = new Entry[numbers.length];
    int size = 0;
    for (int i = 0 ; i < numbers.length ; i++) {
        int nextVal = numbers[i];
        int index = nextVal % entries.length;
        Entry e = entries[index];
        if (e == null) {
            entries[index] = new Entry(nextVal);
            size++;
        } else {
            if(e.insert(nextVal)) {
                size++;
            }
        }
    }
    int[] result = new int[size];
    int index = 0;
    for (int i = 0 ; i < entries.length ; i++) {
        Entry current = entries[i];
        while (current != null) {
            result[i++] = current.value;
            current = current.next;
        }
    }
    return result;
}

public static class Entry {
    int value;
    Entry next;

    Entry(int value) {
        this.value = value;
    }

    public boolean insert(int newVal) {
        Entry current = this;
        Entry prev = null;
        while (current != null) {
            if (current.value == newVal) {
                return false;
            } else if(current.next != null) {
                prev = current;
                current = next;
            }
        }
        prev.next = new Entry(value);
        return true;
    }
}

Note: I am assuming the array is sorted.

Code:

int[] input = new int[]{1, 1, 3, 7, 7, 8, 9, 9, 9, 10};
int current = input[0];
boolean found = false;

for (int i = 0; i < input.length; i++) {
    if (current == input[i] && !found) {
        found = true;
    } else if (current != input[i]) {
        System.out.print(" " + current);
        current = input[i];
        found = false;
    }
}
System.out.print(" " + current);

output:

  1 3 7 8 9 10

You need to sort your array then then loop and remove duplicates. As you cannot use other tools you need to write be code yourself.

You can easily find examples of quicksort in Java on the internet (on which this example is based).

public static void main(String[] args) throws Exception {
    final int[] original = new int[]{1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1};
    System.out.println(Arrays.toString(original));
    quicksort(original);
    System.out.println(Arrays.toString(original));
    final int[] unqiue = new int[original.length];
    int prev = original[0];
    unqiue[0] = prev;
    int count = 1;
    for (int i = 1; i < original.length; ++i) {
        if (original[i] != prev) {
            unqiue[count++] = original[i];
        }
        prev = original[i];
    }
    System.out.println(Arrays.toString(unqiue));
    final int[] compressed = new int[count];
    System.arraycopy(unqiue, 0, compressed, 0, count);
    System.out.println(Arrays.toString(compressed));
}

private static void quicksort(final int[] values) {
    if (values.length == 0) {
        return;
    }
    quicksort(values, 0, values.length - 1);
}

private static void quicksort(final int[] values, final int low, final int high) {
    int i = low, j = high;
    int pivot = values[low + (high - low) / 2];
    while (i <= j) {
        while (values[i] < pivot) {
            i++;
        }
        while (values[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(values, i, j);
            i++;
            j--;
        }
    }
    if (low < j) {
        quicksort(values, low, j);
    }
    if (i < high) {
        quicksort(values, i, high);
    }
}

private static void swap(final int[] values, final int i, final int j) {
    final int temp = values[i];
    values[i] = values[j];
    values[j] = temp;
}

So the process runs in 3 steps.

  1. Sort the array - O(nlgn)
  2. Remove duplicates - O(n)
  3. Compact the array - O(n)

So this improves significantly on your O(n^3) approach.

Output:

[1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1]
[1, 1, 1, 2, 4, 4, 7, 8, 8, 9, 9]
[1, 2, 4, 7, 8, 9, 0, 0, 0, 0, 0]
[1, 2, 4, 7, 8, 9]

EDIT

OP states values inside array doesn't matter really. But I can assume that range is between 0-1000. This is a classic case where an O(n) sort can be used.

We create an array of size range +1, in this case 1001. We then loop over the data and increment the values on each index corresponding to the datapoint.

We can then compact the resulting array, dropping values the have not been incremented. This makes the values unique as we ignore the count.

public static void main(String[] args) throws Exception {
    final int[] original = new int[]{1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1, 1000, 1000};
    System.out.println(Arrays.toString(original));
    final int[] buckets = new int[1001];
    for (final int i : original) {
        buckets[i]++;
    }
    final int[] unique = new int[original.length];
    int count = 0;
    for (int i = 0; i < buckets.length; ++i) {
        if (buckets[i] > 0) {
            unique[count++] = i;
        }
    }
    final int[] compressed = new int[count];
    System.arraycopy(unique, 0, compressed, 0, count);
    System.out.println(Arrays.toString(compressed));
}

Output:

[1, 1, 2, 8, 9, 8, 4, 7, 4, 9, 1, 1000, 1000]
[1, 2, 4, 7, 8, 9, 1000]

Slight modification to the original code itself, by removing the innermost for loop.

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];
                }*/
                arr[j] = arr[end-1];
                end--;
                j--;
            }
        }
    }

    int[] whitelist = new int[end];
    /*for(int i = 0; i < end; i++){
        whitelist[i] = arr[i];
    }*/
    System.arraycopy(arr, 0, whitelist, 0, end);
    return whitelist;
}

We can remove duplicates using heap data structure.

  1. Create a min Heap or Max heap [I use min Heap](Takes O(n))
  2. remove the elements from the heap and store it into another list if that element is not in that list. This takes O(nlog(n)) since we remove an element from the heap and it takes log n we do this until the all n elements removed from the heap n * logn

Overall Time complexity is O(nlog(n)).

Python code for my approach

import heapq

l =[1,2,4,6,3,2,6,1]

heapq.heapify(l)
no_duplicate_list =[]

try:
    while True:
        e = heapq.heappop(l)# will return the minimum value from the heap 
        if no_duplicate_list ==[]:
            no_duplicate_list.append(e)
        else:
            if e == no_duplicate_list[-1]:
                continue
            no_duplicate_list.append(e)
except IndexError as i:
    print(no_duplicate_list) #[1, 2, 3, 4, 6]


Why do all people not check this below lines?

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.

I'm posting very simple implementation with caring the above line.

public class RemoveDuplicates {

public static void main(String[] args) {

    int[] arr = { 1, 2, 3, 4, 2, 3, 1 }; // input array
    int len = arr.length;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < len; j++) {
            if (arr[i] == arr[j]) {
                while (j < (len) - 1) {
                    arr[j] = arr[j - 1];
                    j++;
                }
                len--;
            }
        }
    }
    for (int i = 0; i < len; i++) {
        System.out.print("  " +arr[i]);
    }

   }
 }

Input : 1, 2, 3, 4, 2, 3, 1

Output : 1 2 3 4


What if you create two boolean arrays: 1 for negative values and 1 for positive values and init it all on false.

Then you cycle thorugh the input array and lookup in the arrays if you've encoutered the value already. If not, you add it to the output array and mark it as already used.


int tempvar=0; //Variable for the final array without any duplicates
     int whilecount=0;    //variable for while loop
     while(whilecount<(nsprtable*2)-1) //nsprtable can be any number
     {
//to check whether the next value is idential in case of sorted array       
if(temparray[whilecount]!=temparray[whilecount+1])
        {
            finalarray[tempvar]=temparray[whilecount];
            tempvar++;
            whilecount=whilecount+1;
        }
        else if (temparray[whilecount]==temparray[whilecount+1])
        {
            finalarray[tempvar]=temparray[whilecount];
            tempvar++;
            whilecount=whilecount+2;
        }
     }

Hope this helps or solves the purpose.


There exists many solution of this problem.

  1. The sort approach

    • You sort your array and resolve only unique items
  2. The set approach

    • You declare a HashSet where you put all item then you have only unique ones.
  3. You create a boolean array that represent the items all ready returned, (this depend on your data in the array).

If you deal with large amount of data i would pick the 1. solution. As you do not allocate additional memory and sorting is quite fast. For small set of data the complexity would be n^2 but for large i will be n log n.


Please check this. It will work for both sorted/unsorted array. The complexity is O(n^2) same as bubble sort. Yes the complexity can be improved further with first sort and then binary search. But this is simple enough to work on every cases except negative element (-1). This can also be changed by using large integer value instead of -1.

void remove_duplicates(int *A, int N)

{

int i,j;

for (i=1; i<N; i++) {
    if (A[i] == -1) continue;
    for (j=i+1; j<=N; j++) {
        if (A[i] == A[j])
            A[j] = -1;
    }
}
}

int main() {

int N;
int A[1001];
int i;

printf("Enter N: ");
scanf("%d", &N);
printf("Enter the elements:\n");
for (i=1; i<=N; i++)
    scanf("%d", &A[i]);

remove_duplicates(A, N);
for (i=1; i<=N; i++) {
    if (A[i] == -1)
        continue;
    printf("%d  ", A[i]);
}
printf("\n");

return 0;
}

I have done using sample as 12 elements,

public class Remdup_arr {

public static void main(String[] args) {

    int a[] = {1,1,2,3,4,4,5,6,7,8,6,8};
    for(int p : a)
    {
        System.out.print(p);
        System.out.print("\t");
    }

    System.out.println();
    System.out.println();

    remdup(a);

}

private static void remdup(int[] a) {

    int length = a.length;
    int b[] = new int[11];
    int d = 1;
    b[0]=a[0];
    while(length<13 && length>0)
    {
        int x = a[length-1];
        if(!(contain(b , x)))
            {b[d] = a[length-1];
            d++;}
        length--;


    }

    for( int z = 0;z<b.length;z++){
        System.out.print(b[z]);
        System.out.print("\t");}

}

private static boolean contain(int[] b ,int p) {

    boolean bool = false;
    int len = b.length;
    for(int i = 0;i<len;i++)
    {
        if(p == b[i])
            bool = true;
    }



    return bool;

}

}

output is :- 1 1 2 3 4 4 5 6 7 8 6 8

1 8 6 7 5 4 3 2 0 0 0


package com.pari.practice;

import java.util.HashSet;
import java.util.Iterator;

import com.pari.sort.Sort;

public class RemoveDuplicates {

 /**
 * brute force- o(N square)
 * 
 * @param input
 * @return
 */
public static int[] removeDups(int[] input){
    boolean[] isSame = new boolean[input.length];
    int sameNums = 0;

    for( int i = 0; i < input.length; i++ ){
        for( int j = i+1; j < input.length; j++){
            if( input[j] == input[i] ){ //compare same
                isSame[j] = true;
                sameNums++;
            }
        }
    }

    //compact the array into the result.
    int[] result = new int[input.length-sameNums];
    int count = 0;
    for( int i = 0; i < input.length; i++ ){
        if( isSame[i] == true) {
            continue;
        }
        else{
            result[count] = input[i];
            count++;
        }
    }

    return result;
}

/**
 * set - o(N)
 * does not guarantee order of elements returned - set property
 * 
 * @param input
 * @return
 */
public static int[] removeDups1(int[] input){
    HashSet myset = new HashSet();

    for( int i = 0; i < input.length; i++ ){
        myset.add(input[i]);
    }

    //compact the array into the result.
    int[] result = new int[myset.size()];
    Iterator setitr = myset.iterator();
    int count = 0;
    while( setitr.hasNext() ){
        result[count] = (int) setitr.next();
        count++;
    }

return result;
}

/**
 * quicksort - o(Nlogn)
 * 
 * @param input
 * @return
 */
public static int[] removeDups2(int[] input){
    Sort st = new Sort();
    st.quickSort(input, 0, input.length-1); //input is sorted

    //compact the array into the result.
    int[] intermediateResult = new int[input.length];
    int count = 0;
    int prev = Integer.MIN_VALUE;
    for( int i = 0; i < input.length; i++ ){
        if( input[i] != prev ){
            intermediateResult[count] = input[i];
            count++;
        }
        prev = input[i];
    }

    int[] result = new int[count];
    System.arraycopy(intermediateResult, 0, result, 0, count);

    return result;
}


public static void printArray(int[] input){
    for( int i = 0; i < input.length; i++ ){
        System.out.print(input[i] + " ");
    }
}

public static void main(String[] args){
    int[] input = {5,6,8,0,1,2,5,9,11,0};
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups(input));
    System.out.println();
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups1(input));
    System.out.println();
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups2(input));
}
}

Output: 5 6 8 0 1 2 9 11

0 1 2 5 6 8 9 11

0 1 2 5 6 8 9 11

I have just written the above code for trying out. thanks.


import java.util.Arrays;

public class Practice {

public static void main(String[] args) {
    int a[] = { 1, 3, 3, 4, 2, 1, 5, 6, 7, 7, 8, 10 };
    Arrays.sort(a);
    int j = 0;
    for (int i = 0; i < a.length - 1; i++) {
        if (a[i] != a[i + 1]) {
            a[j] = a[i];
            j++;
        }
    }
    a[j] = a[a.length - 1];
    for (int i = 0; i <= j; i++) {
        System.out.println(a[i]);
    }

}
}
**This is the most simplest way**

This is simple way to sort the elements in the array

public class DublicatesRemove {
    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("enter size of the array");
        int l = Integer.parseInt(br.readLine());
        int[] a = new int[l];
        // insert elements in the array logic
        for (int i = 0; i < l; i++) 
        {
            System.out.println("enter a element");
            int el = Integer.parseInt(br.readLine());
            a[i] = el;
        }
        // sorting elements in the array logic
        for (int i = 0; i < l; i++) 
        {
            for (int j = 0; j < l - 1; j++) 
            {
                if (a[j] > a[j + 1])
                {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        // remove duplicate elements logic
        int b = 0;
        a[b] = a[0];
        for (int i = 1; i < l; i++)
        {
            if (a[b] != a[i])
            {
                b++;
                a[b]=a[i];

            }

        }
        for(int i=0;i<=b;i++)
        {
            System.out.println(a[i]);
        }


    }
}

If you are looking to remove duplicates using the same array and also keeping the time complexity of O(n). Then this should do the trick. Also, would only work if the array is sorted.

function removeDuplicates_sorted(arr){

let j = 0; 

for(let x = 0; x < arr.length - 1; x++){
    
    if(arr[x] != arr[x + 1]){ 
        arr[j++] = arr[x];
    }
}

arr[j++] = arr[arr.length - 1];
arr.length = j;

return arr;

}

Here is for an unsorted array, its O(n) but uses more space complexity then the sorted.

function removeDuplicates_unsorted(arr){

let map = {};
let j = 0;

for(var numbers of arr){
    if(!map[numbers]){
        map[numbers] = 1;
        arr[j++] = numbers;
    }
}

arr.length = j;

return arr;

}


 package javaa;

public class UniqueElementinAnArray 
{

 public static void main(String[] args) 
 {
    int[] a = {10,10,10,10,10,100};
    int[] output = new int[a.length];
    int count = 0;
    int num = 0;

    //Iterate over an array
    for(int i=0; i<a.length; i++)
    {
        num=a[i];
        boolean flag = check(output,num);
        if(flag==false)
        {
            output[count]=num;
            ++count;
        }

    }

    //print the all the elements from an array except zero's (0)
    for (int i : output) 
    {
        if(i!=0 )
            System.out.print(i+"  ");
    }

}

/***
 * If a next number from an array is already exists in unique array then return true else false
 * @param arr   Unique number array. Initially this array is an empty.
 * @param num   Number to be search in unique array. Whether it is duplicate or unique.
 * @return  true: If a number is already exists in an array else false 
 */
public static boolean check(int[] arr, int num)
{
    boolean flag = false;
    for(int i=0;i<arr.length; i++)
    {
        if(arr[i]==num)
        {
            flag = true;
            break;
        }
    }
    return flag;
}

}


If you are allowed to use Java 8 streams:

Arrays.stream(arr).distinct().toArray();

Since you can assume the range is between 0-1000 there is a very simple and efficient solution

//Throws an exception if values are not in the range of 0-1000
public static int[] removeDuplicates(int[] arr) {
    boolean[] set = new boolean[1001]; //values must default to false
    int totalItems = 0;

    for (int i = 0; i < arr.length; ++i) {
        if (!set[arr[i]]) {
            set[arr[i]] = true;
            totalItems++;
        }
    }

    int[] ret = new int[totalItems];
    int c = 0;
    for (int i = 0; i < set.length; ++i) {
        if (set[i]) {
            ret[c++] = i;
        }
    }
    return ret;
}

This runs in linear time O(n). Caveat: the returned array is sorted so if that is illegal then this answer is invalid.


This is an interview question :Remove duplicates from an array.I shall not use any Set or collections. The complete solution is :

public class Test4 {
public static void main(String[] args) {
     int a[] = {1, 2, 2, 3, 3, 3, 6,6,6,6,6,66,7,65}; 
              int newlength =    lengthofarraywithoutduplicates(a);
              for(int i = 0 ; i < newlength ;i++) {
                  System.out.println(a[i]);
              }//for
}//main

private static int lengthofarraywithoutduplicates(int[] a) {
     int count = 1 ;
     for (int i = 1; i < a.length; i++) {
          int ch = a[i];
          if(ch != a[i-1]) {
              a[count++] = ch;
          }//if
    }//for
    return count;

}//fix

}//end1

public class RemoveDuplicates {
public Integer[] returnUniqueNumbers(Integer[] original,
        Integer[] uniqueNumbers) {
    int k = 0;  

    for (int j =  original.length - 1; j >= 0; j--) {
        boolean present = false;
        for (Integer u : uniqueNumbers) {
            if (u != null){
            if(u.equals(original[j])) {
                present = true;
            }}
        }
        if (present == false) {
            uniqueNumbers[k] = original[j];
            k++;
        }
    }
    return uniqueNumbers;
}

public static void main(String args[]) {
    RemoveDuplicates removeDup = new RemoveDuplicates();
    Integer[] original = { 10, 20, 40, 30, 50, 40, 30, 20, 10, 50, 50, 50,20,30,10,40 };
    Integer[] finalValue = new Integer[original.length + 1];

    // method to return unique values
    Integer[] unique = removeDup.returnUniqueNumbers(original, finalValue);

    // iterate to return unique values
    for (Integer u : unique) {
        if (u != null) {
            System.out.println("unique value : " + u);
        }
    }
}}

This code handles unsorted array containing multiple duplicates for same value and returns unique elements.


I feel Android Killer's idea is great, but I just wondered if we can leverage HashMap. So I did a little experiment. And I found HashMap seems faster than HashSet.

Here is code:

    int[] input = new int[1000000];

    for (int i = 0; i < input.length; i++) {
        Random random = new Random();
        input[i] = random.nextInt(200000);
    }

    long startTime1 = new Date().getTime();
    System.out.println("Set start time:" + startTime1);

    Set<Integer> resultSet = new HashSet<Integer>();

    for (int i = 0; i < input.length; i++) {
        resultSet.add(input[i]);
    }

    long endTime1 = new Date().getTime();
    System.out.println("Set end time:"+ endTime1);
    System.out.println("result of set:" + (endTime1 - startTime1));     
    System.out.println("number of Set:" + resultSet.size() + "\n");

    long startTime2 = new Date().getTime();
    System.out.println("Map start time:" + startTime1);

    Map<Integer, Integer> resultMap = new HashMap<Integer, Integer>();

    for (int i = 0; i < input.length; i++) {
        if (!resultMap.containsKey(input[i]))
            resultMap.put(input[i], input[i]);
    }

    long endTime2 = new Date().getTime();
    System.out.println("Map end Time:" + endTime2);
    System.out.println("result of Map:" + (endTime2 - startTime2));
    System.out.println("number of Map:" + resultMap.size());

Here is result:

Set start time:1441960583837
Set end time:1441960583917
result of set:80
number of Set:198652

Map start time:1441960583837
Map end Time:1441960583983
result of Map:66
number of Map:198652

Use the ArrayUtil class as you need. I have written some methods other than removing duplicates. This class is implemented without using any Collection framework classes.

public class ArrayUtils {
/**
 * Removes all duplicate elements from an array. 
 * @param arr Array from which duplicate elements are to be removed.
 * @param removeAllDuplicates true if remove all duplicate values, false otherwise 
 * @return Array of unique elements.
 */
public static int[] removeDuplicate(int[] arr, boolean removeAllDuplicates)         {
    int size = arr.length;

    for (int i = 0; i < size;) {
        boolean flag = false;

        for (int j = i + 1; j < size;) {
            if (arr[i] == arr[j]) {
                flag = true;
                shrinkArray(arr, j, size);
                size--;
            } else
                j++;
        }

        if (flag && removeAllDuplicates) {
            shrinkArray(arr, i, size);
            size--;
        } else
            i++;
    }

    int unique[] = new int[size];
    for (int i = 0; i < size; i++)
        unique[i] = arr[i];

    return unique;
}

/**
 * Removes duplicate elements from an array. 
 * @param arr Array from which duplicate elements are to be removed.
 * @return Array of unique elements.
 */
public static int[] removeDuplicate(int[] arr) {
    return removeDuplicate(arr, false);
}


private static void shrinkArray(int[] arr, int pos, int size) {
    for (int i = pos; i < size - 1; i++) {
        arr[i] = arr[i + 1];
    }
}

/**
 * Displays the array.
 * @param arr The array to be displayed.
 */
public static void displayArray(int arr[]) {
    System.out.println("\n\nThe Array Is:-\n");

    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + "\t");
    }
}

/**
 * Initializes the array with a given value.
 * @param arr The array to be initialized.
 * @param withValue The value with which the array is to be initialized.
 */
public static void initializeArray(int[] arr, int withValue) {
    for (int i = 0; i < arr.length; i++) {
        arr[i] = withValue;
    }
}

/**
 * Checks whether an element is there in the array. 
 * @param arr The array in which the element is to be found.
 * @param element The element that is to be found.
 * @return True if found false otherwise
 */
public static boolean contains(int arr[], int element) {
    for(int i=0; i< arr.length; i++) {
        if(arr[i] == element)
            return true;
    }

    return false;
}

/**
 * Removes a element from an array.
 * @param arr The array from which the element is to removed.
 * @param element The element to be removed
 * @return The size of the array after removing.
 */
public static int removeElement(int[] arr, int element) {
    int size = arr.length;
    for(int i=0; i< arr.length; i++){
        if(arr[i] == element){
            shrinkArray(arr, i, arr.length);
            size--;
        }
    }
    return size;
}

/**
 * Counts unique elements in an array.
 * @param arr The required array.
 * @return Unique element count.
 */
public static int uniqueElementCount(int arr[]) {
    int count = 0;
    int uniqueCount=0;
    int[] consideredElements = new int[arr.length];

    initializeArray(consideredElements, 0);

    for(int i=0;i<arr.length;i++) {
        int element = arr[i];
        for(int j=i+1;j<arr.length; j++){
            if(element != arr[j] && !contains(consideredElements, element)){
                consideredElements[count++] = element;
            }
        }
    }

    for(int i=0;i< consideredElements.length;i++)
        if(consideredElements[i]!=0)
            uniqueCount++;

    return uniqueCount;
}
}

public void removeDup(){ 
String[] arr = {"1","1","2","3","3"};
          boolean exists = false;
          String[] arr2 = new String[arr.length];
          int count1 = 0;
          for(int loop=0;loop<arr.length;loop++)
            {
              String val = arr[loop];
              exists = false;
              for(int loop2=0;loop2<arr2.length;loop2++)
              {     
                  if(arr2[loop2]==null)break;
                  if(arr2[loop2]==val){
                        exists = true;
                }
              }
              if(!exists) {
                    arr2[count1] = val;
                    count1++;
              }
            }
}

How about this one, only for sorted array of numbers, to print array without duplicates, without using Set or other Collections, just Array:

 public static int[] removeDuplicates(int[] array) {
    int[] nums =new int[array.length];
    int addedNum = 0;
    int j=0;
    for(int i=0;i<array.length;i++) {
        if (addedNum != array[i]) {
        nums[j] = array[i];
        j++;
        addedNum = nums[j-1];
        }
    }
    return Arrays.copyOf(nums, j);
}

Array of 1040 duplicated numbers processed in 33020 nanoseconds(0.033020 millisec).


Here is my solution. The time complexity is o(n^2)

public String removeDuplicates(char[] arr) {
        StringBuilder sb = new StringBuilder();

        if (arr == null)
            return null;
        int len = arr.length;

        if (arr.length < 2)
            return sb.append(arr[0]).toString();

        for (int i = 0; i < len; i++) {

            for (int j = i + 1; j < len; j++) {
                if (arr[i] == arr[j]) {
                    arr[j] = 0;

                }
            }
            if (arr[i] != 0)
                sb.append(arr[i]);
        }

        return sb.toString().trim();
    }

Well first answer will be to use hashset which is designed to remove duplicates as Android Killer answer pointed out

Approach 2 :- But if you are not allowed to use set then sort it first with quicksort which will be nlogn and then apply XOR operation to find duplicates

Optimized one

public static void removeDuplicates(int[] arr) {
        int[] input = new int[] { 1, 1, 3, 7, 7, 8, 9, 9, 9, 10 };
        int current = input[0];
        boolean found = false;

        for (int i = 0; i < input.length-1; i++) {

            if((input[i]^input[i+1])==0){
                System.out.println(input[i]);
            }
        }

    }

public class RemoveDuplicates {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int size;
        System.out.println("Enter an array size");
        Scanner sc=new Scanner(System.in);
        size = sc.nextInt();

        int arr[] = new int[size];

        System.out.println("Enter "+size+" numbers");
        for(int i=0;i<size;i++){
            arr[i]=sc.nextInt();
        }

        for(int i=0;i<size;i++){
            int count=0;
            for(int j=i+1;j<size;j++){
                if(arr[i]==arr[j]){

                    int shiftLeft = j;

                    for (int k = j+1; k < size; k++, shiftLeft++) {
                        arr[shiftLeft] = arr[k];
                    }
                    size--;
                    j--;
                }
            }
        }
        System.out.println("New Array");
        for(int i=0;i<size;i++)
        {
            System.out.println(arr[i]);
        }
    }

}

    public static int[] removeDuplicates(int[] input){

        int j = 0;
        int i = 1;
        //return if the array length is less than 2
        if(input.length < 2){
            return input;
        }
        while(i < input.length){
            if(input[i] == input[j]){
                i++;
            }else{
                j = j+1;
                input[j] = input[i];
                i = i+1;
            }    
        }
        int[] output = new int[j+1];
        for(int k=0; k<output.length; k++){
            output[k] = input[k];
        }

        return output;
    }

public static void main(String a[]){
        int[] input1 = {2,3,6,6,8,9,10,10,10,12,12};
        int[] output = removeDuplicates(input1);
        for(int i:output){
            System.out.println(i+" ");
        }
    }

For a sorted Array, just check the next index:

//sorted data!
public static int[] distinct(int[] arr) {
    int[] temp = new int[arr.length];

    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        int current = arr[i];

        if(count > 0 )
            if(temp[count - 1] == current)
                continue;

        temp[count] = current;
        count++;
    }

    int[] whitelist = new int[count];
    System.arraycopy(temp, 0, whitelist, 0, count);

    return whitelist;
}

  public static void main(String[] args) { 
            int input[] = { 1, 5, 1, 0, -3, 1, -3, 2, 1 }; 
            int j = 0; 
            int output[] = new int[100]; 
            Arrays.fill(a, 0); 
            for (int i = 0; i < 9; i++) { 
                    if (output[input[i]] == 0) {
                            input[j++] = input[i]; 
                            output[input[i]]++; 
                    } 
            } 
            for (int i = 0; i < j; i++) { 
                    System.out.print(input[i] + " "); 
            } 
    }

Hope it helps...

if (!checked)//Condition to add into array {
        $scope.selectWeekDays.push(WeekKeys);
    } else {
        for (i = 0; i <= $scope.selectWeekDays.length; i++) // Loop to check IsExists {
            if ($scope.selectWeekDays[i] == WeekKeys)//then if Equals removing by splice {
                $scope.selectWeekDays.splice(i, 1);
                break;
            }
        }
    }

Examples related to java

Under what circumstances can I call findViewById with an Options Menu / Action Bar item? How much should a function trust another function How to implement a simple scenario the OO way Two constructors How do I get some variable from another class in Java? this in equals method How to split a string in two and store it in a field How to do perspective fixing? String index out of range: 4 My eclipse won't open, i download the bundle pack it keeps saying error log

Examples related to arrays

PHP array value passes to next row Use NSInteger as array index How do I show a message in the foreach loop? Objects are not valid as a React child. If you meant to render a collection of children, use an array instead Iterating over arrays in Python 3 Best way to "push" into C# array Sort Array of object by object field in Angular 6 Checking for duplicate strings in JavaScript array what does numpy ndarray shape do? How to round a numpy array?

Examples related to optimization

Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly? Measuring execution time of a function in C++ GROUP BY having MAX date How to efficiently remove duplicates from an array without using Set Storing JSON in database vs. having a new column for each key Read file As String How to write a large buffer into a binary file in C++, fast? Is optimisation level -O3 dangerous in g++? Why is processing a sorted array faster than processing an unsorted array? MySQL my.cnf performance tuning recommendations