CODEWITHSUNDEEP
javaarraylisttime-complexity
user8138142
user8138142

Reputation:

Time complexity of removing duplicates in an ArrayList

I wanted to 'remove' elements in ArrayList by creating a new ArrayList that contains all elements except the duplicates. Duplicates are selected by an comparator and the ordering should be maintained. The algorithm is just iterating over the ArrayList and adding each element that isn't already in the new list. The work is done in a method that is going through the entire ArrayList and checking for equality. Here is the code:

public static <T> ArrayList<T> noDups(Comparator<T> cmp, ArrayList<T> l) {

    ArrayList<T> noDups = new ArrayList<T>();
    for(T o : l) {
        if(!isIn(cmp, o, l)) 
            noDups.add(o);
    }
    return noDups;
}

public static <T> boolean isIn(Comparator<T> cmp, T o, ArrayList<T> l) {
    Iterator<T> i = l.iterator();
    if (o==null) {
        while (i.hasNext())
            if (i.next()==null)
                 return true;
    } else {
        while (!(i.hasNext()))
            if (o.equals(i.next()))
                return true;
    }
    return false;
}

I'm curious about the time complexity this algorithm has. My thoughts are: For the first step there is no work, because the ArrayList noDups is empty. For the second step there is one check, for the third 3 and so on to n-1. So we have 1+2+...+n-1. Is that correct and what time complexity would that be?

Upvotes: 0

Views: 6950

Answers (2)

Fureeish
Fureeish

Reputation: 13424

The time-complexity of your algorithm is O(n^2), since for each element in the array you have to compare it with every single one added before. You can improve that to O(n*log(n)) actually O(n) using a Set.

You mentioned that you care about the order and as far as you know, the HashSet does not maintain it. It's true, but there is a way to make it work. Use LinkedHashSet like so:

ArrayList<Integer> array = 
    new ArrayList<>(Arrays.asList(1, 5, 4, 2, 2, 0, 1, 4, 2));
LinkedHashSet<Integer> set = new LinkedHashSet<>(array);

This will construct a LinkedHashSet, which time-complexity of insertion, deletion and finding is O(1). The important part is the difference between this data structure and your typical HashSet. LinkedHashSet additionally creates a linked list that indicates the order of the elements in terms of insertion.

If you run the above code with this loop:

for(Integer i : set) {
    System.out.print(i + " ");
}

The output will be: 1 5 4 2 0 - as you wanted.

Upvotes: 3

Brian Ellis
Brian Ellis

Reputation: 95

You are correct that the time complexity of this would be O(N^2). However, "a list without duplicates" is the definition of a set. This question has some details on implementation and corner cases that might cover what you're interested in.

Upvotes: 0

Related Questions