Find All Numbers Disappeared in an Array

Find All Numbers Disappeared in an Array

What is this problem about?

The Find All Numbers Disappeared in an Array coding problem provides an array of $n$ integers where each integer is in the range $[1, n]$. Some numbers appear twice and others are missing. You need to find all the numbers in the range $[1, n]$ that do not appear in the array. The challenge is to solve it in $O(N)$ time and $O(1)$ extra space.

Why is this asked in interviews?

This is a high-signal "optimization" question asked by Meta, Microsoft, and Amazon. It tests whether you can use the input array itself to store state information. This Array interview pattern is vital for demonstrating that you can think about memory efficiency. It evaluations your ability to map values to indices and use a non-destructive "marking" technique.

Algorithmic pattern used

This problem uses the Negative Marking interview pattern. Since all numbers are positive and in the range $[1, n]$, the indices $0 \dots n-1$ correspond to the values $1 \dots n$.

1. For each number num in the array, calculate the index idx = abs(num) - 1.
2. Go to nums[idx] and, if it's positive, multiply it by -1 to "mark" that the value idx + 1 has been seen.
3. After one pass, iterate through the array again.
4. Any index i where nums[i] is still positive means the number i + 1 never appeared in the input.

Example explanation

nums = [4, 3, 2, 7, 8, 2, 3, 1] ($n=8$)

1. Process 4: Mark nums[3] as negative.
2. Process 3: Mark nums[2] as negative.
3. ... continue marking ...
4. Final state: nums contains some negative and some positive values.
5. Check index 4: nums[4] is positive. This means 5 is missing.
6. Check index 5: nums[5] is negative. 6 is present. Result: [5, 6].

Common mistakes candidates make

• Using extra space: Using a boolean array or a set, which violates the $O(1)$ space constraint.
• Index errors: Forgetting to use abs(nums[i]) when determining the index to mark, as that value might have already been turned negative by a previous marking.
• Off-by-one: Forgetting that values are 1-based and indices are 0-based.

Interview preparation tip

Problems that involve the range $[1, N]$ are perfect candidates for index-based marking or cyclic sort. Always look for ways to "flag" an index without losing the original value stored at that index.