Nested loop to count duplicates in an ArrayList isn't working properly

Question

I have the following method which takes an ArrayList of strings where each string is a coordinate in the form of "(x, y)". The method is supposed to count the number of times any of these coordinates appears more than once in the list.

Here is my code:

public static int duplicateHouses(ArrayList<String> houses){
        int duplicateCount = 0;

        for(int i = 0; i < houses.size(); i++){
            for(int j = i + 1; j < houses.size(); j++){
                if((houses.get(i)).equals(houses.get(j))){
                    duplicateCount++;
                }
            }
        }

        return duplicateCount;
    }

It ends up returning a number which is far greater than the number of strings in my list. Where am I going wrong?

Answer 1

If you have at least 4 duplicates in your List, the first loop will find 3, the second loop will find 2, the third loop will find 1, which gives a result of 6. Basically, each loop is finding the same duplicates over again.

For example...

public static void main(String[] args) {
    ArrayList<String> houses = new ArrayList<>(25);
    houses.add("(1x1)");
    houses.add("(1x2)");
    houses.add("(1x1)");
    houses.add("(1x3)");
    houses.add("(1x1)");
    houses.add("(1x4)");
    houses.add("(1x1)");
    houses.add("(1x5)");

    System.out.println(houses.size());
    System.out.println(duplicateHouses2(houses));
}

public static int duplicateHouses(ArrayList<String> houses) {
    int duplicateCount = 0;

    for (int i = 0; i < houses.size(); i++) {
        System.out.println("---");
        for (int j = i + 1; j < houses.size(); j++) {
            if ((houses.get(i)).equals(houses.get(j))) {
                System.out.println(i + ": " + houses.get(i) + " == " + j + ": " + houses.get(j));
                duplicateCount++;
            }
        }
    }

    return duplicateCount;
}

Which outputs...

---
0: (1x1) == 2: (1x1)
0: (1x1) == 4: (1x1)
0: (1x1) == 6: (1x1)
---
---
2: (1x1) == 4: (1x1)
2: (1x1) == 6: (1x1)
---
---
4: (1x1) == 6: (1x1)
---
---
---

Now, you could, create a copy of the List and remove each duplicate as you find it or you could use a second List to store the duplicate values.

I tried calculating the difference between a Set of the values and the original List, but this returned a value which was 1 less then expected result (in the above example it returned 3 instead of 4)

Instead, I used a Stream#filter of the original and a Set to generate the duplicate count

For example...

public static int duplicateHouses(ArrayList<String> houses) {
    // Make sure we only have 1 of each possible value
    Set<String> copy = new HashSet<>(houses);
    int duplicateCount = 0;
    // For each value, we want to filter the original 
    // list so that only matching values remain...
    for (String value : copy) {
        Stream<String> filter = houses.stream().filter((String t) -> t.equals(value));
        // If there is more then one, then there are duplicates...
        long count = filter.count();
        if (count > 1) {
            duplicateCount += count;
        }
    }
    return duplicateCount;
}

Which, given the first example, returns 3