Missing Numbers Between Two Lists

Purpose

I came across this relatively simple question on HackerRank regarding finding missing values across two Lists. I took a fairly straight-forward approach, but is there a "better" / "slicker" way of implementing a solution?

Task

Strategy

• Iterate throughList with complete data.

• If Integer is in List with incomplete data, remove Integer from both Lists. Else, add Integer to a TreeSet of all missing values.

Implementation

public class MissingNumbersImpl implements MissingNumbers {
@Override
public Set identifyMissingNumbers(final List all, final List incomplete) {
if (all.size() missingNumbers = new TreeSet<>();

final Iterator iterator = all.iterator();
while (iterator.hasNext()) {
final Integer next = iterator.next();
if (incomplete.contains(next)) {
incomplete.remove(next);
iterator.remove();
} else {
missingNumbers.add(next);
}
}

return missingNumbers;
}
}


Building on the comments made by h.j.k., you forgot to handle one case in your implementation: the case when the bigger list has a count of a number n that is less than the count for that number n for the smaller list. For example, if you consider the following:

public static void main(String[] args) {
    List all = new ArrayList<>(Arrays.asList(1, 1, 2, 3, 4, 5, 5));
    List incomplete = new ArrayList<>(Arrays.asList(1, 1, 1, 2));
    System.out.println(identifyMissingNumbers(all, incomplete));
}

It will print with your current code [3, 4, 5] disregarding 1 as a missing number although it should be missing since it does not appear with the same frequency in both lists.

The reason is that you're iterating on the number in the bigger list, removing them from the smaller list as you encounter them and adding them to the missing number when you finally don't find a match. But if the smaller list as a bigger count for that number, it won't be taken into account.

There are a couple of possibilities to tackle this: you could introduce a new loop that would have the same logic but iterating on the smaller list instead and removing elements from the bigger list.

I find a better approach would be the following:

• Sort each input list in ascending order

• Create an empty Map that will store the count for each number

• Iterate over the first list. If the number if not in the Map, add it with a value of 1. Else, increment the current count by 1.

• Iterate over the second list. If the number if not in the Map, add it with a value of -1. Else, decrement the current count by 1.

• At this point, all values in the map that are different than 0 are missing numbers: since we added 1 when encountered in the first list and subtracted 1 when encountered in the second list, the result must be 0 if that number is not missing. Hence, we remove all entries in the map where the value is 0.

• Finally, we return the keys of the map in ascending order.

Assuming Java 8, an implementation would be the following:

public static Set identifyMissingNumbers(List list1, List list2) {
    Map count = new HashMap<>();
    for (Integer number : list1) {
        count.merge(number, 1, Integer::sum);
    }
    for (Integer number : list2) {
        count.merge(number, -1, Integer::sum);
    }
    count.values().removeIf(i -> i == 0);
    return new TreeSet<>(count.keySet());
}

StackExchange Code Review Q#118719, answer score: 3