Find All Duplicates in an Array

medium array hash map

Problem

Given an integer array nums where 1 ≤ nums[i] ≤ n and n = nums.length, return every element that appears twice. Solve in O(n) time and O(1) extra space (modifying nums is allowed).

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

Output[2, 3]

When we visit a value x, flip nums[|x|−1] negative; a second visit finds it already negative.

nums (comma-separated, values in [1, n])

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

function findDuplicates(nums) {
  const res = [];
  for (const x of nums) {
    const idx = Math.abs(x) - 1;
    if (nums[idx] < 0) res.push(Math.abs(x));
    else nums[idx] = -nums[idx];
  }
  return res;
}

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int x : nums) {
            int idx = Math.abs(x) - 1;
            if (nums[idx] < 0) res.add(Math.abs(x));
            else nums[idx] = -nums[idx];
        }
        return res;
    }
}

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> res;
    for (int x : nums) {
        int idx = abs(x) - 1;
        if (nums[idx] < 0) res.push_back(abs(x));
        else nums[idx] = -nums[idx];
    }
    return res;
}

Explanation

The clever trick here is that the values are all in the range [1, n], so each value can point to its own slot in the array. We use the sign of each slot as a "have I seen this number?" flag, which means we need no extra storage.

For each value x we look at index idx = abs(x) - 1 (we use abs because earlier steps may have flipped numbers negative). That slot is the "home" of the value x.

If nums[idx] is already negative, it means we visited this home before, so x is a duplicate and we add it to the result. If it is still positive, this is the first time we see x, so we flip nums[idx] negative to mark it.

Example: nums = [4, 3, 2, 7, 8, 2, 3, 1]. When we reach the second 2, its home slot (index 1) was already made negative by the first 2, so 2 is recorded; the same happens for 3. The output is [2, 3].

One pass through the array, flipping signs as we go, gives the answer in linear time with no extra memory.

Time: O(n) Space: O(1)