Start practising

Find All Duplicates in an Array

Medium Arrays & Hashing In-place Transformations Original on LeetCode

Find All Duplicates in an Array is a medium arrays & hashing problem solved with the in-place transformations pattern. The best approach, optimal (index marking with signs), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from brute force (hash set) up.

Problem

You get an array of n integers where every value is in [1, n] and appears once or twice. Return all values that appear twice.

Solve it in O(n) time using only constant extra space.

Examples

Example 1

Input
nums = [3, 1, 3, 4, 2, 4]
Output
[3, 4]

Example 2

Input
nums = [1, 2]
Output
[]

Constraints

  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n, each value appears once or twice.
  • O(n) time and constant extra space.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute force (hash set)O(n)O(n)
Optimal (index marking with signs)O(n)O(1)

1Brute force (hash set)

TimeO(n)
SpaceO(n)

Add values to a set; a value already in the set is a duplicate.

  1. For each x: if the set contains x, record it; else add it.
Java
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        List<Integer> out = new ArrayList<>();
        for (int x : nums) if (!seen.add(x)) out.add(x);
        return out;
    }
}

2Optimal (index marking with signs)

TimeO(n)
SpaceO(1)The input array stores the markers; only the output is extra.

For value v, flip nums[v - 1] to negative to mark v as seen. If it is already negative when you arrive, v is a duplicate. Use Math.abs when reading, since earlier steps may have flipped the current cell.

  1. For each i: v = |nums[i]|.
  2. If nums[v - 1] < 0, add v to the answer.
  3. Else set nums[v - 1] = -nums[v - 1].
Java
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int v = Math.abs(nums[i]);
            if (nums[v - 1] < 0) out.add(v);
            else nums[v - 1] = -nums[v - 1];
        }
        return out;
    }
}

Edge cases to test

  • No duplicates
  • Every value duplicated

Hints

Hint 1

Values are 1..n, so every value maps to an index. Can the sign of nums[v - 1] remember that v was seen?

FAQ

What is the best time complexity for Find All Duplicates in an Array?

Optimal (index marking with signs) runs in O(n) time and O(1) extra space.

Which pattern does Find All Duplicates in an Array use?

It is a arrays & hashing problem that uses the in-place transformations pattern. Other problems with the same pattern: Set Matrix Zeroes.

Is there a brute force solution for Find All Duplicates in an Array?

Yes. Brute force (hash set) takes O(n) time and O(n) space. Add values to a set; a value already in the set is a duplicate.

Which edge cases should I test for Find All Duplicates in an Array?

No duplicates; Every value duplicated.