Missing Numbers

Question

Numeros, the Artist, had two lists A and B, such that B was a permutation of A. Numeros was very proud of these lists. Unfortunately, while transporting them from one exhibition to another, some numbers were left out of A. Can you find the missing numbers?

Notes

If a number occurs multiple times in the lists, you must ensure that the frequency of that number in both lists is the same. If that is not the case, then it is also a missing number. You have to print all the missing numbers in ascending order. Print each missing number once, even if it is missing multiple times. The difference between maximum and minimum number in B is less than or equal to 100.

Input Format

There will be four lines of input:

n - the size of the first list This is followed by space-separated integers that make up the first list.

m - the size of the second list This is followed by space-separated integers that make up the second list.

Output Format

Output the missing numbers in ascending order.

Sample Input

10
203 204 205 206 207 208 203 204 205 206
13
203 204 204 205 206 207 205 208 203 206 205 206 204

Sample Output

204 205 206

public class Solution {
 private static List<Integer> getMissing(int[] A, int[] B) {
 Map<Integer, Integer> freqA = new HashMap<>();
 Map<Integer, Integer> freqB = new HashMap<>();
 for (int i = 0; i < A.length; i++) {
 Integer count = freqA.get(A[i]);
 if (count == null) {
 count = 0;
 }
 freqA.put(A[i], count + 1);
 }
 for (int i = 0; i < B.length; i++) {
 Integer count = freqB.get(B[i]);
 if (count == null) {
 count = 0;
 }
 freqB.put(B[i], count + 1);
 }
 List<Integer> missing = new ArrayList<>();
 for (Map.Entry<Integer, Integer> entry : freqB.entrySet()) {
 int count = entry.getValue();
 int number = entry.getKey();
 if (freqA.get(number) == null ||
 freqA.get(number) < count) {
 missing.add(number);
 }
 }
 Collections.sort(missing);
 return missing;
 }
 public static void main(String[] args) {
 Scanner s = new Scanner(System.in);
 int N = s.nextInt();
 int []A = new int[N];
 for (int i = 0; i < N; i++) {
 A[i] = s.nextInt();
 }
 int M = s.nextInt();
 int []B = new int[M];
 for (int i = 0; i < M; i++) {
 B[i] = s.nextInt();
 }
 List<Integer> result = getMissing(A, B);
 for (int item : result) {
 System.out.print(item + " ");
 }
 }
}

• greybeard: max(B) - min(B) ≤ 100 gives the opportunity to use something much simpler than a HashMap.
• CodeYogi: @greybeard example please.
• greybeard: example [for something much simpler than a HashMap] please use an integer array counts of 201 elements. With the first element from A, establish final int offset = A[0] - 100. For each element a of A, increase the element count[a - offset]++ - decrease for elements of B. For every index i with count[i] < 0, report i + offset.
• paparazzo: I would do a sort and then enumerate each at the same time
• CodeYogi: @Paparazzi you solution would be slower in that case.

Answer 1

Where are the doc comments?

Your naming is intuitive, the formatting familiar.

If you used freqA.merge(i, 1, Integer::sum); (thanks, h.j.k.), I wouldn't have considered factoring out histogram collection.
If using Maps that can be constructed with an expected size provided, do so.
I'm convinced using one histogram Map is better: smaller memory footprint, no need to "filter" entries. Downside: separate Maps opened a promising opportunity for concurrency where my half-assed timings indicate adding a parallel() to h.j.k.'s approach to just slow things down.

Using a sorted Map vs. a fast one and sorting the results is an interesting choice.

You can combine both using a modified counting sort:

/** largest value - smallest */
static final int SPAN = 100;
/** Enumerates numbers that occur less often
 * in the first array than in the second, in ascending order.
 * max(B) - min(B) <= SPAN
 * @param A array with numbers missing
 * @param B array defining the complete multiset
 * @return numbers that occur less often in <code>A</code>
 * than in <code>B</code>, in ascending order */
public static int[] getMissing(int[] A, int[] B) {
 final int // using SPAN+1 elements only required "min[B]"
 counts[] = new int[SPAN*2+1],
 offset = B[0] - SPAN;
 for (int a: A)
 counts[a-offset]++;
 for (int b: B)
 counts[b-offset]--;
// dually use counts to keep the missing numbers
 int nMissing = 0,
 missing[] = counts;
 for (int i = 0; i < counts.length; i++)
 if (counts[i] < 0)
 missing[nMissing++] = i + offset;
 return java.util.Arrays.copyOf(missing, nMissing);
}

— alas, at least I and CodeYogi have mis-read the problem statement:
The numbers in A are a subsequence of B. One solution looks similar:

/** largest value - smallest */
static final int SPAN = 100;
/** Enumerates numbers missing in the sequence of values in
 * the first array compared to the second, in ascending order.
 * max(B) - min(B) <= SPAN
 * @param A array with numbers missing
 * @param B array defining the complete sequence
 * @return numbers missing in the sequence of values in
 * <code>A</code>compared to <code>B</code>,
 * in ascending order */
public static int[] getMissing(int[] A, int[] B) {
 final boolean isMissing[] = new boolean[SPAN*2+1];
 final int offset = B[0] - SPAN;
 for (int a = 0, b = 0 ; b < B.length ; b++)
 if (A.length <= a || A[a] != B[b])
 isMissing[B[b]-offset] = true;
 else
 a++;
 int nMissing = 0,
 missing[] = new int[SPAN+1];
 for (int i = 0; i < isMissing.length; i++)
 if (isMissing[i])
 missing[nMissing++] = i + offset;
 return java.util.Arrays.copyOf(missing, nMissing);
}

(Planting a sentinel at the end of A to avoid the length check looked too messy.)

• Bastien Aracil: This seems to assume that B[0] is the minimal value in the array. Even though this is true in the example, there is no evidence that is always the case.
• greybeard: @BastienAracil Note that "the arrays" are almost twice the quoted limit in difference between values in B, and B[0] gets offset to the middle.

Answer 2

@coderodde's answer is a good start for a Map-based solution, but there's room for more refactoring by:

1. Using a Map implementation with ordered keys, such as TreeMap.
2. Populating the map with the longer array values first, so that the subtraction step afterwards can immediately remove values which are not missing.

We will then have:

private static int[] diff(int[] a, int[] b) {
 int[] shorter = a.length > b.length ? b : a;
 int[] longer = a.length > b.length ? a : b;
 Map<Integer, Integer> map = new TreeMap<>();
 IntStream.of(longer).forEach(x -> map.merge(x, 1, Integer::sum));
 IntStream.of(shorter).forEach(
 x -> map.computeIfPresent(x, (k, v) -> v == 1 ? null : v - 1));
 return map.keySet().stream().mapToInt(Integer::intValue).toArray();
}

This relies on Map.merge(K, V, BiFunction) that lets us either add 1 to the map for new values, or increment the existing by 1. We use Map.computeIfAbsent(K, BiFunction) to do the removal when the current value is 1, else we decrement the existing by 1. Finally, when we stream() on the keySet(), we know that it's already sorted, so we can return the results immediately after a quick int[] conversion.

Also, as hinted by @greybeard's comment, there's probably a simpler/more efficient solution since \$m, n\$ are given, but the suggestion above is decent enough by my books. :)

• greybeard: Having computeIfPresent() remove non-missing numbers is a nice touch.

Answer 3

You can do it using only one hash map. Load the frequencies from the B array into that only map. Then, iterate over the first A array and subtract each element from the frequency map. Finally, iterate over the map. If the frequency of an element is larger than zero, the element is missing in the first A array.

My version looks like this:

public static List<Integer> getMissing2(int[] array1, int[] array2) {
 Map<Integer, Integer> frequencyMap = new HashMap<>();
 List<Integer> missingNumberList = new ArrayList<>();
 IntStream.of(array2)
 .forEach((int i) -> 
 { frequencyMap.put(i, frequencyMap.getOrDefault(i, 0) + 1); });
 IntStream.of(array1)
 .forEach((int i) -> 
 { frequencyMap.put(i, frequencyMap.get(i) - 1);});
 frequencyMap.entrySet()
 .stream()
 .forEach(
 (Map.Entry<Integer, Integer> entry) -> 
 { if (entry.getValue() > 0) {
 missingNumberList.add(entry.getKey());
 }});
 Collections.sort(missingNumberList);
 return missingNumberList;
}

Also, you can do

System.out.println(result);

instead of the for loop printing the number one at a time.

Hope that helps.

• greybeard: frequencyMap.put(i, frequencyMap.getOrDefault(i, 0) + 1) you got to be kidding.
• coderodde: @greybeard What's wrong with it?
• greybeard: What's wrong with [using map.put(key, f(map.get(key)))]? put(get()) does two lookups, map.compute(key, bif) doesn't need to.
• h.j.k.: @coderodde there's Map.merge(K, V, BiFunction). :)