Increase efficiency of finding and using duplicate elements in an ArrayList

user_15585458 0
Viewed 63

My task is to take an ArrayList<SomeType>, and check for duplicate elements. If there is a duplicate element found && it has the same someClassProperty as the first element, use the duplicate element as a parameter in a function call. In the end, remove the duplicates from the original List and the function returns the number of duplicates. (Sorry if my explanation is poor, please look at my code then it's easy to understand)

The problem here is that the code I've come up with is very inefficient and slow, I can't figure out how to make it faster.

public int removeDuplicateElements(){
    List<SomeType> duplicates = new ArrayList<SomeType>();
    for (int i = 0; i < ListWithDuplicates.size(); i++) {
        SomeType firstElement = ListWithDuplicates.get(i);
        for (int j = i + 1; j < ListWithDuplicates.size(); j++) {
            SomeType otherElement = ListWithDuplicates.get(j);
            assert firstElement != otherElement;
            if (firstElement.sameProperty(otherElement.getProperty())) {
                duplicates.add(otherElement);
                firstElement.someFunction(otherElement);
            }
        }
    }
    for (SomeType duplicate : duplicates) {
        ListWithDuplicates.remove(duplicate);
    }
    return duplicates.size();
}
arraylist data-structures java
3 Answers

Assuming your property implements hashCode() and equals(), you can use it as a key in a HashMap to efficiently exclude duplicates and construct a new list from the remaining values:

public int removeDuplicateElements() {
    Map<Property, SomeType> uniques = new HashMap<>();
    for (SomeType element : ListWithDuplicates) {
        uniques.putIfAbsent(element.getProperty(), element);
    }
    int duplicates = ListWithDuplicates.size() - uniques.size();
    ListWithDuplicates = new ArrayList<>(uniques.values());
    return duplicates;
}

A more streamy variant on the above map:

Map<Property, SomeProperty> uniques = ListWithDuplicates.stream()
        .collect(Collectors.toMap(SomeType::getProperty, e -> e, (a, b) -> a));
user_15538510

You code runs in O(n^2) time complexity, we can reduce the time complexity by two ways

Sorting the Array

 public static <T extends Comparable<T>> int removeDuplicateElements(List<T> listWithDuplicates) {
        Collections.sort(listWithDuplicates);
        for(int i = 0 ; i < listWithDuplicates.size() - 1 ; i++) {
            if(listWithDuplicates.get(i).equals(listWithDuplicates.get(i+1))) {
                listWithDuplicates.remove(i--);
            }
        }
        return listWithDuplicates.size();
    }

By doing it this way, we reduce the Time Complexity to O(nlogn) but we lose the order of the original array.

Hash Table

public static <T extends Comparable<T>> int removeDuplicateElements(List<T> listWithDuplicates) {
        HashMap<T,Boolean> hashMap = new HashMap<>();
        for(int i = 0 ; i < listWithDuplicates.size() ; i++) {
            if(hashMap.containsKey(listWithDuplicates.get(i)))
                listWithDuplicates.remove(i--);
            else
                hashMap.put(listWithDuplicates.get(i),true);
        }
        return listWithDuplicates.size();
    }

With this way we reduce the time complexity to O(n) but we exchanged it for O(n) memomry complexity.

user_91427290

Note: Existing solution may count the same duplicates several times, thus the number of actual duplicates is miscalculated if the duplicate element is simply added to duplicates list.

An example: input contains 3 elements, all having the same property X, then for element1 two duplicates element2 and element3 are detected, and for element2 the duplicate element3 is detected, thus listWithDuplicates contains 3 entries and one of them is duplicated again.

The duplicates may be detected and collected with O(N) time complexity when using a map Map<SomeProperty, List<SomeType>>, however, additional memory is required for this.

If someFunction needs to be invoked for all predecessors as in the example above:

element1.someFunction(element2);
element1.someFunction(element3);
element2.someFunction(element3);

the following solution may be offered, however, in the worst case it has the same O(N^2) complexity.

public int removeDuplicateElements(List<SomeType> input){
    Map<SomeProperty, List<SomeType>> map = input.stream()
        .collect(Collectors.grouping(SomeType::getProperty));
        
    int size = input.size();
    
    map.values().stream() // Stream<List<SomeType>>
        .filter(lst -> lst.size() > 1) // address only duplicated elements
        .forEach(lst -> {
            for (int i = 0; i < lst.size() - 1; i++) {
                for (int j = i + 1; j < lst.size(); j++) {
                    lst.get(i).someFunction(lst.get(j));
                    input.remove(lst.get(j));
                }
            }
        });
    
    return size - input.size();
}

If someFunction needs to be invoked only for the first element a simpler and faster solution using Collectors.toMap can be created:

public int removeDuplicateElements(List<SomeType> input){
    Map<SomeProperty, List<SomeType>> map = input.stream()
        .collect(Collectors.toMap(
            SomeType::getProperty,
            x -> x,
            (a, b) -> {a.someFunction(b); return a;}
    ));
        
    int size = input.size();
    
    input.retainAll(map.values());
    
    return size - input.size();
}
user_132798310
Related