Find All Duplicates in an Array

Find All Duplicates in an Array looks like a job for a hash set — but it hides a beautiful constraint that lets you solve it in O(1) extra space. The trick is index marking: use the array itself as your memory.

The slow way first

The obvious idea: keep a hash set (or a count map). For each number, check if it is already in the set; if so, it is a duplicate, otherwise add it. That is O(n) time — but it uses O(n) extra space, and the problem explicitly asks for none.

The question to ask: what do I already have that could store the bookkeeping for free? The array itself. The values are all in 1..n, so each value can point at a unique slot — and a slot can carry one extra bit of information by its sign.

The idea: let each value mark its own slot

Every value v is in 1..n, so v "owns" the slot at index v - 1. We walk the array and, for each value x, look at the owned slot i = abs(x) - 1:

• If nums[i] is positive, this is the first time we have seen the value abs(x). Flip the sign of nums[i] to negative to mark it visited.
• If nums[i] is already negative, we have visited that slot before — so abs(x) is a duplicate. Collect it.

We use abs(x) everywhere because earlier steps may have flipped the very cell we are reading, and we must recover the original value.

The sign is a free extra bit of storage: positive means "not yet seen," negative means "seen once." No hash map required.

Walk through it

Step through the animation. The pointer x scans left to right; the pointer i = abs(x)-1 jumps to the slot each value owns. The first time a slot is touched it turns negative (visited). When x lands on a slot that is already negative, we have found a duplicate and add abs(x) to res. For [1, 3, 3, 2, 1] we catch 3 on the third value and 1 on the last, returning [3, 1].

Pseudocode

res = empty list
for each value x in nums:
    i = abs(x) - 1               # the slot this value owns
    if nums[i] < 0:              # slot already marked?
        add (i + 1) to res        # abs(x) is a duplicate
    else:
        nums[i] = -nums[i]        # mark the slot visited
return res

The Python solution

def find_duplicates(nums):
    res = []
    for x in nums:
        i = abs(x) - 1
        if nums[i] < 0:
            res.append(i + 1)
        else:
            nums[i] *= -1
    return res

• res collects the answers; no other data structure is allocated.
• i = abs(x) - 1 is the slot the current value owns. We take abs because an earlier step may have already flipped x to negative.
• if nums[i] < 0 is the visited check — the slot's sign is our one bit of memory.
• res.append(i + 1) records the duplicate. The owned value is i + 1, which equals abs(x).
• nums[i] *= -1 marks the slot visited the first time we reach it.

Complexity

We match the hash set on time, O(n), but use only O(1) extra space (ignoring the output list). The whole trick is reusing the input as scratch storage — a move that only works because the values are bounded by 1..n.

When this pattern shows up

Practice