Loading…

mediumArraysSometimes asked

Missing Numbers

Q: How do you solve Missing Numbers using the Baseline — Set Difference (Loses Multiplicity) approach?

When to use it: Bring it up to expose the duplicate trap: it looks right but silently drops numbers that are only partially missing. Drop every reduced value into a hash set, then collect the original values that aren't in that set. **Why it's tempting.** 'Missing' sounds like 'not present', and set difference is the textbook tool for 'in A but not in B'. For a problem where each value appears at most once, this is exactly right. **Why it's wrong here.** Duplicates matter. Take `original = [7, 7, 5]` and `reduced = [7, 5]`. The set of reduced values is `{7, 5}`, so the set approach finds *nothing* missing — yet one copy of `7` was clearly removed. A set records only presence, not how many, so it can't see a partial loss. **The fix.** Replace 'is it present?' with 'how many?'. Count occurrences in both arrays; a value is missing whenever its original count exceeds its reduced count. That's the frequency-difference approach. Time complexity: O(n + m). Space complexity: O(n).

Q: How do you solve Missing Numbers using the Frequency-Count Difference (Optimal) approach?

When to use it: The intended answer: count both arrays and report values whose original count exceeds the reduced count. Tally occurrences of every value in both arrays, then report each value whose original count exceeds its reduced count. **Why counts, not sets.** Missing means 'fewer copies than before'. If the original has `countOrig[v]` copies and the reduced array has `countRed[v]`, then `countOrig[v] − countRed[v]` copies of `v` were removed. Any value with a positive difference is missing. This respects multiplicity exactly, which set difference cannot. **Why iterate the original's keys.** The problem guarantees every reduced value also appears in the original, so the original's key set is a superset. Walking the original's distinct values (or the whole bounded range) guarantees we never miss a candidate, and `countRed.get(v, 0)` safely returns 0 for values that were entirely removed. **Why a count array beats a hash map here.** The constraint `max − min ≤ 100` means all values fit in a window of 101 slots. Offsetting each value by `min` lets you index a fixed-size array directly — `O(1)` updates with no hashing overhead. A hash map also works and is the natural choice when the range is unknown; the count array is the constant-factor optimization the bounded range invites. **Why distinct and sorted.** The output is the *set* of values that lost at least one copy, presented in ascending order. Even if a value lost three copies, it appears once in the answer. Iterating a count array from low to high index naturally yields sorted, distinct output for free. **Why not sum or XOR.** The `sum`/XOR tricks recover a *single* missing number from a complete range. With several distinct numbers missing — and duplicates in play — those identities collapse multiple unknowns into one equation and can't separate them. The count difference is the general tool. Time complexity: O(n + m). Space complexity: O(n).

Arrays & Hashing · 48 of 83 · 7 min

Given two arrays of integers, find which elements of the original array are missing from the reduced array. Numbers may occur multiple times; a number is missing as many times as the original has more copies than the reduced one.

Return the distinct missing numbers in ascending order. It is guaranteed every value in the reduced array also appears in the original, and the range of values satisfies max − min ≤ 100.

In plain English

Two multisets: the original and a reduced version with some copies removed. A value is missing when the original contains strictly more of it than the reduced array does. We report each such value once, in ascending order — the *set* of values that lost at least one copy.

Examples

Example 1

Input: original = [7,2,5,3,5,3], reduced = [7,2,5,3]
Output: [3, 5]
Note: Original counts: {7:1, 2:1, 5:2, 3:2}. Reduced counts: {7:1, 2:1, 5:1, 3:1}. Both 5 and 3 lost one copy, so the distinct missing values sorted are [3, 5].

Example 2

Input: original = [7, 7, 5, 9, 5], reduced = [7, 5, 9]
Output: [5, 7]
Note: Original has two 7s and two 5s; reduced has one each. So 7 and 5 each lost a copy → missing = [5, 7] sorted.

Constraints

1 ≤ n, m ≤ 2 × 10⁵ (sizes of reduced and original arrays)
Every reduced element appears in the original
0 ≤ value ≤ 10⁴
max(original) − min(original) ≤ 100

Clarifying questions4First question: Can a number be missing even if it's still in the reduced array?Explore questions

Q1.Can a number be missing even if it's still in the reduced array?
Yes. If the original has 3 copies of 7 and the reduced has 2, then 7 is missing (one copy lost). That's why we compare counts, not membership.
Q2.Should the output contain duplicates?
No — return the distinct values that are missing, each once, sorted ascending.
Q3.Is the value range bounded?
Yes: max − min ≤ 100. That lets you use a fixed-size count array offset by the minimum for O(1) constant factors.
Q4.Could the reduced array have a number not in the original?
No, the problem guarantees every reduced element exists in the original, so we only iterate the original's keys.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You're given the original array and a reduced copy that's missing some elements (with possible duplicates). Find which numbers are missing, counting multiplicity. Tally counts of both arrays in frequency maps, then a number is missing if its count in the original exceeds its count in the reduced one. Return the distinct missing values sorted ascending. Counting both arrays is O(n + m); the answer set is small.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you handle multiplicity correctly — a number can be 'missing' even if it still appears in the reduced array — and whether you exploit the bounded value range for an O(n) count-array solution.

Where candidates slip

Using set difference (ignores duplicates) or summing/ XOR-ing the arrays (works for one missing number, not several). Also forgetting to return the result sorted and de-duplicated.

How to stand out

Point out the duplicate trap explicitly, note the bounded range lets you skip the hash map for a count array, and confirm the output must be distinct and sorted.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Set Difference (Loses Multiplicity)	`O(n + m)`	`O(n)`	Bring it up to expose the duplicate trap: it looks right but silently drops numbers that are only partially missing.	Read
2	Frequency-Count Difference (Optimal)Optimal	`O(n + m)`	`O(n)`	The intended answer: count both arrays and report values whose original count exceeds the reduced count.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previeworiginal[]for each value v in A: A[v] > B[v] ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Set Difference (Loses Multiplicity)

TimeO(n + m)SpaceO(n)

Bring it up to expose the duplicate trap: it looks right but silently drops numbers that are only partially missing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Your first instinct might be: put the reduced array in a set, then report originals not in that set.

2Hint 2Explore hint

Consider original = [7, 7, 5], reduced = [7, 5]. Is 7 'missing'? The set approach says no — is that right?

3Hint 3Explore hint

What information does a set throw away that you actually need here?

A · Core idea

Drop every reduced value into a hash set, then collect the original values that aren't in that set.

Why it's tempting. 'Missing' sounds like 'not present', and set difference is the textbook tool for 'in A but not in B'. For a problem where each value appears at most once, this is exactly right.

Why it's wrong here. Duplicates matter. Take original = [7, 7, 5] and reduced = [7, 5]. The set of reduced values is {7, 5}, so the set approach finds nothing missing — yet one copy of 7 was clearly removed. A set records only presence, not how many, so it can't see a partial loss.

The fix. Replace 'is it present?' with 'how many?'. Count occurrences in both arrays; a value is missing whenever its original count exceeds its reduced count. That's the frequency-difference approach.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

original = [7, 7, 5], reduced = [7, 5]

Hash-map state

lookup 7

lookup 7

ValueIndex / state

7→ present

5→ present

Match found

7 in set → 'not missing'

Final result[] (incorrect — should be [7])

C · Code with teaching comments

Reference implementation previewpublic List<Integer> missingNumbers(int[] reduced, int[] original) { Set<Integer> present = new HashSet<>(); for (int x : reduced) present.add(x); TreeSet<Integer> missing = new TreeSet<>(); for (int x : original) {Explore the full code

solution.javaJava

Baseline — Set Difference (Loses Multiplicity) — reference

2 teaching notes

1
public List<Integer> missingNumbers(int[] reduced, int[] original) {
2
    // A set stores presence only — it cannot represent 'two copies of 7'.
3
    Set<Integer> present = new HashSet<>();
4
    for (int x : reduced) present.add(x);
5
    TreeSet<Integer> missing = new TreeSet<>();
6
    for (int x : original) {
7
        // Misses values that lost some but not all copies — the core bug.
8
        if (!present.contains(x)) missing.add(x);
9
    }
10
    return new ArrayList<>(missing); // WRONG: ignores multiplicity
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n + m) timeO(n) spaceOpen the invariant and proofExplore the proof

The trap is reading 'missing' as 'absent'. The problem actually means 'fewer copies than before', which only a count comparison — not set membership — can detect.

ComplexityO(n + m) time, O(n) space — Building the set and scanning the original are each linear, so O(n + m) time — but the answer is wrong because sets discard counts.

E · Edge cases and pitfalls5no duplicates anywhere — Set difference happens to be correct only because every count is 0 or 1.Explore edge cases

Edge cases handled

no duplicates anywhereSet difference happens to be correct only because every count is 0 or 1.
a value fully removedCaught correctly — but partial removals are missed.

Pitfalls

Treating 'missing' as 'absent' and ignoring multiplicity.
Returning numbers in arbitrary (set) order instead of sorted.
Believing the linear runtime means the answer is correct — it's fast but wrong.

03.2

Approach 2 of 2 · Optimal

Frequency-Count Difference (Optimal)

TimeO(n + m)SpaceO(n)

The intended answer: count both arrays and report values whose original count exceeds the reduced count.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of presence, track how many of each value each array has.

2Hint 2Explore hint

A value is missing when its count in the original is strictly greater than its count in the reduced array.

3Hint 3Explore hint

The value range is bounded (max − min ≤ 100), so a fixed-size count array works — and remember to sort and de-duplicate the output.

A · Core idea

Tally occurrences of every value in both arrays, then report each value whose original count exceeds its reduced count.

Why counts, not sets. Missing means 'fewer copies than before'. If the original has countOrig[v] copies and the reduced array has countRed[v], then countOrig[v] − countRed[v] copies of v were removed. Any value with a positive difference is missing. This respects multiplicity exactly, which set difference cannot.

Why iterate the original's keys. The problem guarantees every reduced value also appears in the original, so the original's key set is a superset. Walking the original's distinct values (or the whole bounded range) guarantees we never miss a candidate, and countRed.get(v, 0) safely returns 0 for values that were entirely removed.

Why a count array beats a hash map here. The constraint max − min ≤ 100 means all values fit in a window of 101 slots. Offsetting each value by min lets you index a fixed-size array directly — O(1) updates with no hashing overhead. A hash map also works and is the natural choice when the range is unknown; the count array is the constant-factor optimization the bounded range invites.

Why distinct and sorted. The output is the set of values that lost at least one copy, presented in ascending order. Even if a value lost three copies, it appears once in the answer. Iterating a count array from low to high index naturally yields sorted, distinct output for free.

Why not sum or XOR. The sum/XOR tricks recover a single missing number from a complete range. With several distinct numbers missing — and duplicates in play — those identities collapse multiple unknowns into one equation and can't separate them. The count difference is the general tool.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

original = [7, 7, 5, 9, 5], reduced = [7, 5, 9]

Hash-map state

compare 5

ValueIndex / state

5→ 2 / 1

Match found

orig 2 vs red 1 → missing

Final result[5, 7]

C · Code with teaching comments

solution.javaJava

Frequency-Count Difference (Optimal) — optimal

3 teaching notes

1
public List<Integer> missingNumbers(int[] reduced, int[] original) {
2
    Map<Integer, Integer> countOrig = new HashMap<>();
3
    // Tally the original multiset's counts in one pass.
4
    for (int x : original) countOrig.merge(x, 1, Integer::sum);
5
    Map<Integer, Integer> countRed = new HashMap<>();
6
    for (int x : reduced) countRed.merge(x, 1, Integer::sum);
7
 
8
    // A TreeSet gives distinct, ascending output for free.
9
    TreeSet<Integer> missing = new TreeSet<>();
10
    for (Map.Entry<Integer, Integer> e : countOrig.entrySet()) {
11
        // Strictly greater means at least one copy was removed; getOrDefault handles
12
        // fully-absent values.
13
        if (e.getValue() > countRed.getOrDefault(e.getKey(), 0)) {
14
            missing.add(e.getKey());
15
        }
16
    }
17
    return new ArrayList<>(missing);
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n + m) timeO(n) spaceOpen the invariant and proofExplore the proof

Comparing two multisets by frequency is the workhorse behind anagram checks, 'find the difference', and ransom-note problems. The mental model: a hash map (or bounded count array) turns 'how many of each?' into O(1) lookups, and the answer is wherever the two tallies disagree.

ComplexityO(n + m) time, O(n) space — Counting each array is one pass: O(n + m). Comparing counts iterates the distinct values (at most the range size or number of keys). Sorting the small result set is negligible. Total O(n + m).

E · Edge cases and pitfalls5value entirely removed — countRed.get(v, 0) returns 0; original count > 0 → reported.Explore edge cases

Edge cases handled

value entirely removedcountRed.get(v, 0) returns 0; original count > 0 → reported.
no numbers removedEvery count matches; missing list is empty.

Pitfalls

Using >= instead of > and reporting values that weren't actually removed.
Returning the result unsorted or with duplicates.
Trying sum/XOR shortcuts, which can't separate several distinct missing values.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<Integer> missingNumbers(int[] reduced, int[] original) { Map<Integer, Integer> countOrig = new HashMap<>(); for (int x : original) countOrig.merge(x, 1, Integer::sum); Map<Integer, Integer> countRed = new HashMap<>(); for (int x : reduced) countRed.merge(x, 1, Integer::sum);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Set difference drops multiplicity

A set records presence, not count, so a value that lost some-but-not-all copies looks 'present' and is never reported.

Explore the code comparison

Don't write this

present = set(reduced)
missing = {x for x in original if x not in present}

Write this instead

from collections import Counter
co, cr = Counter(original), Counter(reduced)
missing = [v for v in co if co[v] > cr[v]]

Unsorted / duplicated output

The problem wants distinct values ascending; a raw list of differences may repeat values or be in arbitrary order.

Explore the code comparison

Don't write this

List<Integer> missing = new ArrayList<>();
// add keys as found, no ordering or de-dup

Write this instead

TreeSet<Integer> missing = new TreeSet<>();
// distinct + ascending by construction

Sum/XOR shortcut

Summing or XOR-ing recovers exactly one missing number from a full range; with several distinct missing values it conflates them.

Explore the code comparison

Don't write this

missing_value = sum(original) - sum(reduced)  # one number only

Write this instead

co, cr = Counter(original), Counter(reduced)
missing = sorted(v for v in co if co[v] > cr[v])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency-count difference between two multisets

Code pattern to memorize

countOrig = Counter(original)
countRed  = Counter(reduced)
missing = sorted(v for v in countOrig if countOrig[v] > countRed.get(v, 0))

Rules to remember

1Compare counts, not membership — a value present in both can still be missing if the original has more copies.
2Return the distinct missing values, sorted ascending — duplicates in the output are not wanted, only the set of values.
3Because values lie within a bounded range (max − min ≤ 100), you can use a fixed-size count array instead of a hash map for O(1) constant-factor speed.
4Iterate keys from the original's map — anything in the reduced array also appears in the original by problem definition.
5Don't subtract sums or use XOR — those collapse multiplicity and fail when several distinct numbers are missing.

Use this pattern when

Find what's missing/extra between two multisets where duplicates matter
Compare two collections by element multiplicity, not just presence
Values are bounded, so a count array gives linear time with a tiny constant

Choose another pattern when

Exactly one number is missing from a 0..n permutation → sum formula or XOR is simpler
You only care about set membership, not counts → a plain hash set difference
The streams are huge and unbounded and you need approximate counts → sketches, not exact maps

Interview takeaway

When 'what's missing' must respect duplicates, compare frequencies: count both multisets and report values whose original count beats their reduced count. Sum/XOR tricks break with multiplicity; the count-difference is the general, O(n) answer.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFrequency-count difference between two multisets. Tally both, then report values whose counts disagree. Respects multiplicity where set difference and sum/XOR tricks fail. A bounded value range lets you swap the hash map for an O(1) count array.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Find All Numbers Disappeared in an Array
Single array of 1..n with some missing — index-marking gives O(1) extra space.
Valid Anagram
Coming soon
Same frequency-count comparison, asking whether two multisets are identical.
Ransom Note
Coming soon
Check one multiset's counts cover another's — the same count-difference idea.

Same pattern

←

Maximum Hourglass Sum

Continue · Next problem

New Year Chaos

mediumArraysSometimes asked

Missing Numbers

Arrays & Hashing · 48 of 83 · 7 min

In plain English

Examples

Example 1

Input: original = [7,2,5,3,5,3], reduced = [7,2,5,3]
Output: [3, 5]
Note: Original counts: {7:1, 2:1, 5:2, 3:2}. Reduced counts: {7:1, 2:1, 5:1, 3:1}. Both 5 and 3 lost one copy, so the distinct missing values sorted are [3, 5].

Example 2

Input: original = [7, 7, 5, 9, 5], reduced = [7, 5, 9]
Output: [5, 7]
Note: Original has two 7s and two 5s; reduced has one each. So 7 and 5 each lost a copy → missing = [5, 7] sorted.

Constraints

1 ≤ n, m ≤ 2 × 10⁵ (sizes of reduced and original arrays)
Every reduced element appears in the original
0 ≤ value ≤ 10⁴
max(original) − min(original) ≤ 100

Clarifying questions4First question: Can a number be missing even if it's still in the reduced array?Explore questions

Q1.Can a number be missing even if it's still in the reduced array?
Yes. If the original has 3 copies of 7 and the reduced has 2, then 7 is missing (one copy lost). That's why we compare counts, not membership.
Q2.Should the output contain duplicates?
No — return the distinct values that are missing, each once, sorted ascending.
Q3.Is the value range bounded?
Yes: max − min ≤ 100. That lets you use a fixed-size count array offset by the minimum for O(1) constant factors.
Q4.Could the reduced array have a number not in the original?
No, the problem guarantees every reduced element exists in the original, so we only iterate the original's keys.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Using set difference (ignores duplicates) or summing/ XOR-ing the arrays (works for one missing number, not several). Also forgetting to return the result sorted and de-duplicated.

How to stand out

Point out the duplicate trap explicitly, note the bounded range lets you skip the hash map for a count array, and confirm the output must be distinct and sorted.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Set Difference (Loses Multiplicity)	`O(n + m)`	`O(n)`	Bring it up to expose the duplicate trap: it looks right but silently drops numbers that are only partially missing.	Read
2	Frequency-Count Difference (Optimal)Optimal	`O(n + m)`	`O(n)`	The intended answer: count both arrays and report values whose original count exceeds the reduced count.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Set Difference (Loses Multiplicity)

TimeO(n + m)SpaceO(n)

Bring it up to expose the duplicate trap: it looks right but silently drops numbers that are only partially missing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Your first instinct might be: put the reduced array in a set, then report originals not in that set.

2Hint 2Explore hint

Consider original = [7, 7, 5], reduced = [7, 5]. Is 7 'missing'? The set approach says no — is that right?

3Hint 3Explore hint

What information does a set throw away that you actually need here?

A · Core idea

Drop every reduced value into a hash set, then collect the original values that aren't in that set.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

original = [7, 7, 5], reduced = [7, 5]

Hash-map state

lookup 7

lookup 7

ValueIndex / state

7→ present

5→ present

Match found

7 in set → 'not missing'

Final result[] (incorrect — should be [7])

C · Code with teaching comments

solution.javaJava

Baseline — Set Difference (Loses Multiplicity) — reference

2 teaching notes

1
public List<Integer> missingNumbers(int[] reduced, int[] original) {
2
    // A set stores presence only — it cannot represent 'two copies of 7'.
3
    Set<Integer> present = new HashSet<>();
4
    for (int x : reduced) present.add(x);
5
    TreeSet<Integer> missing = new TreeSet<>();
6
    for (int x : original) {
7
        // Misses values that lost some but not all copies — the core bug.
8
        if (!present.contains(x)) missing.add(x);
9
    }
10
    return new ArrayList<>(missing); // WRONG: ignores multiplicity
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n + m) timeO(n) spaceOpen the invariant and proofExplore the proof

The trap is reading 'missing' as 'absent'. The problem actually means 'fewer copies than before', which only a count comparison — not set membership — can detect.

ComplexityO(n + m) time, O(n) space — Building the set and scanning the original are each linear, so O(n + m) time — but the answer is wrong because sets discard counts.

E · Edge cases and pitfalls5no duplicates anywhere — Set difference happens to be correct only because every count is 0 or 1.Explore edge cases

Edge cases handled

no duplicates anywhereSet difference happens to be correct only because every count is 0 or 1.
a value fully removedCaught correctly — but partial removals are missed.

Pitfalls

Treating 'missing' as 'absent' and ignoring multiplicity.
Returning numbers in arbitrary (set) order instead of sorted.
Believing the linear runtime means the answer is correct — it's fast but wrong.

03.2

Approach 2 of 2 · Optimal

Frequency-Count Difference (Optimal)

TimeO(n + m)SpaceO(n)

The intended answer: count both arrays and report values whose original count exceeds the reduced count.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of presence, track how many of each value each array has.

2Hint 2Explore hint

A value is missing when its count in the original is strictly greater than its count in the reduced array.

3Hint 3Explore hint

The value range is bounded (max − min ≤ 100), so a fixed-size count array works — and remember to sort and de-duplicate the output.

A · Core idea

Tally occurrences of every value in both arrays, then report each value whose original count exceeds its reduced count.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

original = [7, 7, 5, 9, 5], reduced = [7, 5, 9]

Hash-map state

compare 5

ValueIndex / state

5→ 2 / 1

Match found

orig 2 vs red 1 → missing

Final result[5, 7]

C · Code with teaching comments

solution.javaJava

Frequency-Count Difference (Optimal) — optimal

3 teaching notes

1
public List<Integer> missingNumbers(int[] reduced, int[] original) {
2
    Map<Integer, Integer> countOrig = new HashMap<>();
3
    // Tally the original multiset's counts in one pass.
4
    for (int x : original) countOrig.merge(x, 1, Integer::sum);
5
    Map<Integer, Integer> countRed = new HashMap<>();
6
    for (int x : reduced) countRed.merge(x, 1, Integer::sum);
7
 
8
    // A TreeSet gives distinct, ascending output for free.
9
    TreeSet<Integer> missing = new TreeSet<>();
10
    for (Map.Entry<Integer, Integer> e : countOrig.entrySet()) {
11
        // Strictly greater means at least one copy was removed; getOrDefault handles
12
        // fully-absent values.
13
        if (e.getValue() > countRed.getOrDefault(e.getKey(), 0)) {
14
            missing.add(e.getKey());
15
        }
16
    }
17
    return new ArrayList<>(missing);
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n + m) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5value entirely removed — countRed.get(v, 0) returns 0; original count > 0 → reported.Explore edge cases

Edge cases handled

value entirely removedcountRed.get(v, 0) returns 0; original count > 0 → reported.
no numbers removedEvery count matches; missing list is empty.

Pitfalls

Using >= instead of > and reporting values that weren't actually removed.
Returning the result unsorted or with duplicates.
Trying sum/XOR shortcuts, which can't separate several distinct missing values.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Set difference drops multiplicity

A set records presence, not count, so a value that lost some-but-not-all copies looks 'present' and is never reported.

Explore the code comparison

Don't write this

present = set(reduced)
missing = {x for x in original if x not in present}

Write this instead

from collections import Counter
co, cr = Counter(original), Counter(reduced)
missing = [v for v in co if co[v] > cr[v]]

Unsorted / duplicated output

The problem wants distinct values ascending; a raw list of differences may repeat values or be in arbitrary order.

Explore the code comparison

Don't write this

List<Integer> missing = new ArrayList<>();
// add keys as found, no ordering or de-dup

Write this instead

TreeSet<Integer> missing = new TreeSet<>();
// distinct + ascending by construction

Sum/XOR shortcut

Summing or XOR-ing recovers exactly one missing number from a full range; with several distinct missing values it conflates them.

Explore the code comparison

Don't write this

missing_value = sum(original) - sum(reduced)  # one number only

Write this instead

co, cr = Counter(original), Counter(reduced)
missing = sorted(v for v in co if co[v] > cr[v])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency-count difference between two multisets

Code pattern to memorize

countOrig = Counter(original)
countRed  = Counter(reduced)
missing = sorted(v for v in countOrig if countOrig[v] > countRed.get(v, 0))

Rules to remember

1Compare counts, not membership — a value present in both can still be missing if the original has more copies.
2Return the distinct missing values, sorted ascending — duplicates in the output are not wanted, only the set of values.
3Because values lie within a bounded range (max − min ≤ 100), you can use a fixed-size count array instead of a hash map for O(1) constant-factor speed.
4Iterate keys from the original's map — anything in the reduced array also appears in the original by problem definition.
5Don't subtract sums or use XOR — those collapse multiplicity and fail when several distinct numbers are missing.

Use this pattern when

Find what's missing/extra between two multisets where duplicates matter
Compare two collections by element multiplicity, not just presence
Values are bounded, so a count array gives linear time with a tiny constant

Choose another pattern when

Exactly one number is missing from a 0..n permutation → sum formula or XOR is simpler
You only care about set membership, not counts → a plain hash set difference
The streams are huge and unbounded and you need approximate counts → sketches, not exact maps

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Find All Numbers Disappeared in an Array
Single array of 1..n with some missing — index-marking gives O(1) extra space.
Valid Anagram
Coming soon
Same frequency-count comparison, asking whether two multisets are identical.
Ransom Note
Coming soon
Check one multiset's counts cover another's — the same count-difference idea.

Same pattern

←

Maximum Hourglass Sum

Continue · Next problem

New Year Chaos