How to count single occurrences of elements in an ArrayList?

Question

I am trying to find which numbers appear once in a list. For example, a list of [1, 3, 2, 3] should return [1, 2]. However, my code only returns [1], and when I also tried printing duplicates, it printed [3, 2].

I'm not sure where I'm going wrong since I'm keeping track of duplicates to ensure that I don't count an element twice.

Is there also a more efficient way to do this? For example, with a HashMap? I know there's the Collections class that I can use but I'd rather avoid that, for practice!

Any help and advice would be appreciated.

This is what I have below:

import java.util.*;

class Main {
  public static void main(String[] args) {
    // From a list find which numbers appear once
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(3);
    list.add(2);
    list.add(3);

    ArrayList<Integer> once = new ArrayList<Integer>();
    boolean isDuplicate = false;
    ArrayList<Integer> duplicate = new ArrayList<Integer>();

    for (int i=0; i<list.size(); i++) {
      if (!duplicate.contains(list.get(i))){ // if its not a duplicate, continue iterating through the list
        for (int j=i+1; j<list.size(); j++) {
          if (list.get(i).equals(list.get(j))) { // if its a duplicate
            isDuplicate = true;
          }
        }
        if (!isDuplicate) { // if its not a duplicate add to the "once" list
            once.add(list.get(i));
        } else { // if isDuplicate is true add to the duplicate list
            duplicate.add(list.get(i));
        }
          }
    }
    System.out.println("Numbers that appear once: " + once + "\nDuplicates: " + duplicate);
}

Answer 1

You can compare the return values of the methods indexOf and lastIndexOf, and filter out duplicates:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(2);
list.add(3);

ArrayList<Integer> distinct = list.stream()
        .filter(e -> list.indexOf(e) == list.lastIndexOf(e))
        .collect(Collectors.toCollection(ArrayList::new));

System.out.println(distinct); // [1, 2]

Answer 2

For your code in particular you will need to reset isDuplicate to false at the beginning of each iteration, also, you can add a break statement after you set isDuplicate to true to avoid the verification for the rest of the numbers if you already know that is a duplicate:

for (int i=0; i<list.size(); i++) {
    isDuplicate = false; // reset the variable to false
    if (!duplicate.contains(list.get(i))){
        for (int j=i+1; j<list.size(); j++) {
            if (list.get(i).equals(list.get(j))) {
                isDuplicate = true;
                break; // stops the execution of the current for
            }
        }
        if (!isDuplicate) {
            once.add(list.get(i));
        } else {
            duplicate.add(list.get(i));
        }
    }
}

For the question if there is a most efficient way to do this, there are many ways, but one of the simplest is without using a nested for, you can just ask if the number is present in the once list, and if it is, it means is duplicated, then you can remove it and add it to the duplicate list, like this (In this solution duplicate must be of type Set<Integer> to avoid duplicates if the number is present more than twice in the original list):

for(Integer number : list) {
    if (!once.contains(number) && !duplicate.contains(number)) {
        once.add(number);
    } else {
        once.remove(number);
        duplicate.add(number);
    }
}

Answer 3

The answer is late, but generally it is recommended to use Set to efficiently detect duplicates due to the fact that add method for a set returns false when the element is already present in the set, so there's no need to use contains method.

Set<Integer> once = new LinkedHashSet<>(); // use LinkedHashMap to keep insertion order
Set<Integer> duplicates = new LinkedHashSet<>();
for (Integer i : list) {
    if (!once.add(i)) { // duplicate detected
        duplicates.add(i);
    }
}
once.removeAll(duplicates); // remove all duplicates from `once` set
System.out.println("once: " + once);
System.out.println("duplicates: " + duplicates);

Output:

once: [1, 2]
duplicates: [3]

It is also possible to use Java Stream API (Java 8+) to build a frequency map using such collectors as groupingBy and summingInt to keep the count int or just toMap. Then the map entries can be filtered by the frequency value: if 1, it's a single, else (frequency > 1) it's duplicate.

Map<Integer, Integer> frequencyMap1 = list.stream()
                                          .collect(Collectors.groupingBy(
                                              x -> x, 
                                              LinkedHashMap::new, 
                                              Collectors.summingInt(x -> 1)
                                          ));
System.out.println("groupingBy: " + frequencyMap1);

Map<Integer, Integer> frequencyMap = list.stream()
                                         .collect(Collectors.toMap(
                                             x -> x, x -> 1, Integer::sum, LinkedHashMap::new
                                         ));
System.out.println("toMap: " + frequencyMap);
System.out.println("once: " + frequencyMap.entrySet().stream().filter(e -> e.getValue() == 1).map(Map.Entry::getKey).collect(Collectors.toList()));
System.out.println("duplicates: " + frequencyMap.entrySet().stream().filter(e -> e.getValue() > 1).map(Map.Entry::getKey).collect(Collectors.toList()));

Output:

groupingBy: {1=1, 3=2, 2=1}
toMap: {1=1, 3=2, 2=1}
once: [1, 2]
duplicates: [3]

Answer 4

You need to reset isDuplicate to false

import java.util.*;

class Main {
  public static void main(String[] args) {
    // From a list find which numbers appear once
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(3);
    list.add(2);
    list.add(3);

    ArrayList<Integer> once = new ArrayList<Integer>();
    boolean isDuplicate = false;
    ArrayList<Integer> duplicate = new ArrayList<Integer>();

    for (int i=0; i<list.size(); i++) {
      if (!duplicate.contains(list.get(i))){ // if its not a duplicate, continue iterating through the list
        for (int j=i+1; j<list.size(); j++) {
          if (list.get(i).equals(list.get(j))) { // if its a duplicate
            isDuplicate = true;
          }
        }
        if (!isDuplicate) { // if its not a duplicate add to the "once" list
          once.add(list.get(i));
        } else { // if isDuplicate is true add to the duplicate list
          duplicate.add(list.get(i));
          isDuplicate = false;
        }
      }
    }
    System.out.println("Numbers that appear once: " + once + "\nDuplicates: " + duplicate);
  }
}

Answer 5

Lets's say you have this list:

ArrayList list = new ArrayList();

...

You want to keep the numbers in the list if they only occur once. So we have to remove the number if it is a duplicate.

If you only have a number once in your list, then the first and the last occurence of the number will be the same. We will use this to remove all duplicates from the list:

list.removeIf((number)->list.indexOf(number)!=list.lastIndexOf(number));