LeetCode 442: Find All Duplicates in an Array

Problem Restatement

We are given an integer array nums.

The array has length n.

Every number satisfies:

1 <= nums[i] <= n

Each integer appears either:

We need to return all numbers that appear exactly twice.

The solution must use:

The official problem guarantees every integer appears once or twice, and values are within [1, n]. (leetcode.com)

Input and Output

Example function shape:

def findDuplicates(nums: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums = [4,3,2,7,8,2,3,1]

The duplicated numbers are:

2
3

Answer:

[2, 3]

Example 2:

nums = [1,1,2]

The number 1 appears twice.

Answer:

[1]

Example 3:

nums = [1]

No duplicates exist.

Answer:

[]

First Thought: Use a Hash Set

A simple solution is:

1. Use a set called seen.
2. Traverse the array.
3. If the number already exists in seen, add it to the answer.
4. Otherwise insert it into seen.

Example:

seen = set()

This works in linear time.

However, it uses extra memory proportional to n.

The problem explicitly asks for constant extra space.

Key Insight

The array values lie between:

1 and n

This is extremely important.

Because every value can map directly to an array index.

For a number x, its corresponding index is:

x - 1

We can use the sign of nums[x - 1] as a visited marker.

For example:

nums = [4,3,2,7,8,2,3,1]

When we see 4:

index = 4 - 1 = 3

We negate:

nums[3]

to mark that 4 has been seen.

Later, when we encounter another 2:

index = 2 - 1 = 1

If:

nums[1]

is already negative, then 2 has already appeared before, so 2 is a duplicate.

This lets us store visitation information directly inside the input array.

Algorithm

Initialize an empty answer list.

Traverse every number in nums.

For each value:

1. Compute:

index = abs(num) - 1

We use abs because some values may already be negative.

2. If:

nums[index] < 0

then we have already visited this number before, so it is duplicated.

Append:

index + 1

to the answer.

3. Otherwise, negate:

nums[index]

to mark the number as seen.

Return the answer list.

Correctness

Each number x maps uniquely to index:

x - 1

Initially, all array values are positive.

When the algorithm sees x for the first time, it negates the value at index x - 1. Therefore, after the first occurrence of x, the value at that index becomes negative.

When the algorithm later sees x again, the value at index x - 1 is already negative. This means x has appeared before, so x is duplicated and is added to the answer.

Because every number appears at most twice, each duplicate is added exactly once.

No non-duplicate number is added, because its mapped index becomes negative only after its first occurrence, and no second occurrence exists.

Therefore, the algorithm returns exactly all duplicated numbers.

Complexity

The input array itself is reused as marking storage.

Implementation

class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        duplicates = []

        for num in nums:
            index = abs(num) - 1

            if nums[index] < 0:
                duplicates.append(index + 1)
            else:
                nums[index] = -nums[index]

        return duplicates

Code Explanation

We store duplicates here:

duplicates = []

For each number:

for num in nums:

we compute its mapped index:

index = abs(num) - 1

The abs is necessary because the array values may already have been negated earlier.

If the mapped position is already negative:

if nums[index] < 0:

then this number has appeared before.

So we add the original number:

duplicates.append(index + 1)

Otherwise, we mark it as visited:

nums[index] = -nums[index]

Finally, we return all detected duplicates.

Testing

def run_tests():
    s = Solution()

    assert sorted(
        s.findDuplicates([4,3,2,7,8,2,3,1])
    ) == [2, 3]

    assert s.findDuplicates([1,1,2]) == [1]

    assert s.findDuplicates([1]) == []

    assert sorted(
        s.findDuplicates([2,2,3,3])
    ) == [2, 3]

    assert s.findDuplicates([5,4,6,7,9,3,10,9,5,6]) == [9, 5, 6]

    print("all tests passed")

run_tests()

Test meaning: