Find All Duplicates in an Array

MediumProblemExternal linkUpdated Oct 25, 2026

Description

You get an array nums of n integers, where each nums[i] is in the range [1, n] and each integer appears once or twice.

Return all the integers that appear twice, in any order.

Your solution must run in O(n) time and use only constant extra space (the returned list doesn't count).

Examples

Example 1

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

Output: [2,3]

Explanation: 2 and 3 each appear twice; every other value appears once.

Example 2

Input: nums = [1, 1, 2]

Output: [1]

Explanation: 1 appears twice and 2 once.

Example 3

Input: nums = [1]

Output: []

Explanation: One value, appearing once: nothing appears twice.

Constraints

n == nums.length
1 ≤ n ≤ 10^5
1 ≤ nums[i] ≤ n
Each element in nums appears once or twice.

Editorial

Brute Force

Intuition

Count each value from 1 to n by scanning the array for it. The ones you count twice are the answer.

Step-by-Step Explanation

Let's count every value in nums = [4, 3, 2, 7, 8, 2, 3, 1]:

Scan all 8 values for 1. It appears once.
Scan all 8 values for 2. It appears twice, so 2 goes in the answer.
Scan all 8 values for 3. It appears twice, so 3 goes in the answer.
Scan all 8 values for 4. It appears once.
Scan all 8 values for 5. It appears nowhere.
Scan all 8 values for 6. It appears nowhere.
Scan all 8 values for 7. It appears once.
Scan all 8 values for 8. It appears once.

The values that appear twice are [2, 3].

Count Every Value — Each step scans the array for one value; green marks where it appears.

Algorithm

For each value v from 1 to n: count how many times it appears in nums.
If it appears twice, add v to the answer.

Code

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<int> twice;
        for (int v = 1; v <= n; v++)            // count each value with a full scan
            if (count(nums.begin(), nums.end(), v) == 2) twice.push_back(v);
        return twice;
    }
};

class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        twice = []
        for v in range(1, len(nums) + 1):       # count each value with a full scan
            count = 0
            for x in nums:
                if x == v:
                    count += 1
            if count == 2:
                twice.append(v)
        return twice

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> twice = new ArrayList<>();
        for (int v = 1; v <= nums.length; v++) {        // count each value with a full scan
            int count = 0;
            for (int x : nums)
                if (x == v) count++;
            if (count == 2) twice.add(v);
        }
        return twice;
    }
}

var findDuplicates = function(nums) {
    const twice = [];
    for (let v = 1; v <= nums.length; v++) {    // count each value with a full scan
        let count = 0;
        for (const x of nums)
            if (x === v) count++;
        if (count === 2) twice.push(v);
    }
    return twice;
};

Complexity Analysis

Time Complexity: O(n²)

Each of the n values scans all n entries.

Space Complexity: O(1) besides the answer

Why This Approach Is Not Efficient

At n = 10^5 that's 10^10 comparisons (over the time limit in C++, Python, JavaScript).

A set of the values seen so far finds each copy in one step (O(n) in all), but it costs O(n) extra memory, which the problem rules out. The way out is in the constraint: the values are 1 to n and there are n slots, so every value already has a slot of its own.

Optimal Approach - Cyclic Sort

Intuition

Give each value v a home: index v − 1. Walk the slots, and at each one keep swapping the value there to its home until the slot holds a value whose home already holds it: either the value is home, or it's a copy, because its home is taken by the same value.

When every slot has been visited, every value that appears is in its home, and nothing else can move. The slots that don't hold their own value hold the copies, and those are exactly the values that appear twice.

It's O(n) even with the loop inside the loop: each swap puts one value in its home for good, a value at home never moves again, and only n values can be home.

Step-by-Step Explanation

Let's send the values of nums = [4, 3, 2, 7, 8, 2, 3, 1] home:

The values are 1 to 8, so value v has a home, index v − 1. Send each one home.
Send 4 home to index 3, swapping it with 7. Look at 7, now at index 0.
Send 7 home to index 6, swapping it with 3. Look at 3, now at index 0.
Send 3 home to index 2, swapping it with 2. Look at 2, now at index 0.
Send 2 home to index 1, swapping it with 3. Look at 3, now at index 0.
3's home, index 2, already holds a 3, so this one is a copy. Leave it and move on.
2 is already home at index 1. Move on.
3 is already home at index 2. Move on.
4 is already home at index 3. Move on.
Send 8 home to index 7, swapping it with 1. Look at 1, now at index 4.
Send 1 home to index 0, swapping it with 3. Look at 3, now at index 4.
3's home, index 2, already holds a 3, so this one is a copy. Leave it and move on.
2's home, index 1, already holds a 2, so this one is a copy. Leave it and move on.
7 is already home at index 6. Move on.
8 is already home at index 7. Move on.
Every value is home or a copy. The slots that don't hold their own value, 4 and 5, hold the copies, 3 and 2. 6 swaps in all.

Send Every Value Home — Each swap sends a value to its home index (green). At the end, the slots that don't hold their own value hold the copies.

Algorithm

For each index i: while nums[nums[i] − 1] != nums[i], swap nums[i] with nums[nums[i] − 1] (read v = nums[i] first).
Return every nums[i] where nums[i] != i + 1.

Code

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        for (int i = 0; i < (int)nums.size(); i++) {
            while (nums[nums[i] - 1] != nums[i])        // nums[i]'s home doesn't hold it yet: send it there
                swap(nums[i], nums[nums[i] - 1]);
        }
        vector<int> twice;
        for (int i = 0; i < (int)nums.size(); i++)
            if (nums[i] != i + 1) twice.push_back(nums[i]);   // each wrong slot holds a second copy
        return twice;
    }
};

class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        for i in range(len(nums)):
            while nums[nums[i] - 1] != nums[i]:     # nums[i]'s home doesn't hold it yet: send it there
                v = nums[i]                         # read v first: the swap changes nums[i]
                nums[i], nums[v - 1] = nums[v - 1], v
        return [v for i, v in enumerate(nums) if v != i + 1]   # each wrong slot holds a second copy

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[nums[i] - 1] != nums[i]) {      // nums[i]'s home doesn't hold it yet: send it there
                int v = nums[i];
                nums[i] = nums[v - 1];
                nums[v - 1] = v;
            }
        }
        List<Integer> twice = new ArrayList<>();
        for (int i = 0; i < nums.length; i++)
            if (nums[i] != i + 1) twice.add(nums[i]);   // each wrong slot holds a second copy
        return twice;
    }
}

var findDuplicates = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        while (nums[nums[i] - 1] !== nums[i]) {     // nums[i]'s home doesn't hold it yet: send it there
            const v = nums[i];
            nums[i] = nums[v - 1];
            nums[v - 1] = v;
        }
    }
    const twice = [];
    for (let i = 0; i < nums.length; i++)
        if (nums[i] !== i + 1) twice.push(nums[i]);   // each wrong slot holds a second copy
    return twice;
};

Complexity Analysis

Time Complexity: O(n)

At most n swaps in the whole run (6 for Example 1), plus one scan.

Space Complexity: O(1)

Besides the answer; the values are rearranged in nums itself.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

One swap per slot. if nums[nums[i] - 1] != nums[i]:

On nums = [4, 3, 2, 7, 8, 2, 3, 1] it returns [1,2,3,7]; the answer is [2,3]. After a swap, the value that lands at slot i still has to go home, and if never looks at it again. Values left out of place make their slots look wrong, and the scan reports values that appear once. Keep swapping at slot i with while.

Python's one-line swap. nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]

On nums = [2, 1] it never finishes (the run hit the time limit); the answer is []. Python assigns left to right: nums[i] changes first, so nums[nums[i] - 1] on the left then uses the new value and writes to the wrong slot. On some inputs nothing ever moves and the loop never ends. Read v = nums[i] before the swap.

Reporting the missing values. return [i + 1 for i, v in enumerate(nums) if v != i + 1]

On nums = [4, 3, 2, 7, 8, 2, 3, 1] it returns [5,6]; the answer is [2,3]. A wrong slot i means two things: the copy sitting there, nums[i], appears twice, and i + 1 never appears. The question asks for the copies.

Recording a copy every time it's seen. twice.append(v)

On nums = [4, 3, 2, 7, 8, 2, 3, 1] it returns [2,3,3]; the answer is [2,3]. A copy can be moved by a later swap and hit the "home already holds it" check again at another slot, so it gets recorded twice. Read the copies once, after every value is home.

Where This Pattern Is Taught

This problem practises cyclic sort, where every value 1 to n is sent to its own slot. It's taught in Cyclic Sort, along with First Missing Positive and Find Missing and Repeated Values.