Find All Duplicates in an Array

Find All Duplicates in an Array

What is this problem about?

The Find All Duplicates in an Array coding problem provides an integer array of length $n$ where each integer is in the range $[1, n]$. Each integer appears either once or twice. Your goal is to return an array of all the integers that appear twice. The significant constraint here is to do it in $O(N)$ time and without using any extra space (aside from the output array).

Why is this asked in interviews?

This is a classic "In-place" manipulation problem frequently asked by Apple, Microsoft, and Amazon. It tests whether you can use the input array itself as a data structure to store state. It evaluation your understanding of how to map values to indices, which is a common optimization technique in low-level system programming where memory is restricted. The Array interview pattern of using sign-flipping is a high-signal indicator of a candidate's ability to optimize for space.

Algorithmic pattern used

This problem uses the Negative Marking interview pattern. Since all numbers are in the range $[1, n]$, you can treat each value as an index (offset by 1).

1. Iterate through the array.
2. For each value $x$, treat $|x|-1$ as an index.
3. Check the value at nums[|x|-1].
4. If it's positive, multiply it by -1 to "mark" that you have seen $x$.
5. If it's already negative, it means you have seen $x$ before. Add $|x|$ to your result list.

Example explanation

Array: [4, 3, 2, 7, 8, 2, 3, 1]

1. At index 0 (val 4): Mark index 3 (4-1) as negative. nums[3] becomes -7.
2. At index 1 (val 3): Mark index 2 (3-1) as negative. nums[2] becomes -2.
3. ... continue ...
4. At index 5 (val 2): Check index 1 (2-1). nums[1] is already negative? Wait, if we use indices correctly:
   • Val 2 $o$ index 1. nums[1] was marked negative when we processed the first '3'.
   • This means '2' appeared before? No, the index represents the value. Let's re-trace:

• Value 2 $o$ check nums[1].
• Value 2 (again) $o$ check nums[1]. If it's already negative, '2' is a duplicate.

Common mistakes candidates make

• Using a Hash Set: While a set solves the problem in $O(N)$, it uses $O(N)$ extra space, violating the primary constraint of the problem.
• Index out of bounds: Forgetting to use the absolute value of the current element before using it as an index, as it might have been flipped by a previous step.
• Off-by-one errors: Forgetting that values are $1 \dots n$ while indices are $0 \dots n-1$.

Interview preparation tip

Whenever you see a problem with values in the range $[1, N]$ and a constraint of $O(1)$ space, your mind should immediately jump to "Array as a Hash Table" or "Cyclic Sort" patterns. These are the only ways to track state without extra memory.