Find All Duplicates in an Array

How it works

Since all values are in the range [1, n] where n is the array length, we can use the array itself as a hash map. The key insight is that each value v can be mapped to index v-1. When we encounter a value, we mark the element at its corresponding index as negative. If we encounter a value whose corresponding index is already negative, that value must be a duplicate.

Steps

1. For each number in the array:
   • Compute the index as abs(num) - 1.
   • If nums[idx] is already negative, add abs(num) to the result (this value was seen before).
   • Negate nums[idx] to mark that we have seen the value idx + 1.
2. Return the result list.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting to Use Absolute Value When Accessing Indices

In the negative marking approach, once a value at an index is negated, subsequent accesses using that value as an index will fail. Always use abs(num) - 1 to compute the correct index, as the value itself may have been negated in a previous iteration.

Off-by-One Index Errors

Since array values are in the range [1, n] but indices are [0, n-1], you must subtract 1 when converting a value to an index. Forgetting this adjustment causes index out of bounds errors or marks the wrong positions.

Modifying the Array When It Should Be Preserved

The negative marking approach modifies the input array in place. If the problem requires the original array to remain unchanged, or if the array is used elsewhere after the function call, you should either restore the array afterward or use a different approach like a hash set.

from typing import List

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

        for num in nums:
            idx = abs(num) - 1
            if nums[idx] < 0:
                res.append(abs(num))
            nums[idx] = -nums[idx]

        return res

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;

        for (int num : nums) {
            int idx = abs(num) - 1;
            if (nums[idx] < 0) {
                res.push_back(abs(num));
            }
            nums[idx] = -nums[idx];
        }

        return res;
    }
};