What is the brute force approach and complexity for Find All Duplicates in an Array?

For each i, look for an equal value at some j > i with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Find All Duplicates in an Array?

Swap each value v home to index v − 1; values not at home are duplicates with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Find All Duplicates in an Array?

Look for key signals in the prompt: "values between 1 and n" indicates Each value has a home index v − 1 inside the array.; "appears once or twice" indicates At most one extra copy per value — it will be the one left out of place.; "O(1) extra space" indicates No count array or hash set — the input must store "seen" itself.; "return all duplicates" indicates Read the answer off every misplaced slot, not just the first one..

Find All Duplicates in an Array

Medium·LeetCode #442Basic Anchor

LeetCode

Jump:

30-Second Mental ModelCyclic Sort — Duplicate number (squatters after placement)

Complexity:O(N²)→O(N)

Key Insight

Use the array itself as the count array. Value v has the home nums[v − 1]. Swap every value home. A value that appears once ends up at its home. For a value that appears twice, one copy gets home and the other cannot — its home is taken by its twin. That stuck copy sits at some wrong index. So after placement, every i with nums[i] != i + 1 holds a duplicate.

Core Validity Invariant

Keep swapping nums[i] home while nums[i] != nums[nums[i] − 1]. After that, every index with nums[i] != i + 1 holds a duplicate value.

Problem

You are given an array nums of length n. Every value is between 1 and n, and every value appears once or twice.

Return every value that appears twice. The order of the answer does not matter.

Your algorithm must run in O(N) time and use only O(1) extra space (the output list does not count).

Input

An integer array nums of length n, with 1 ≤ nums[i] ≤ n.

Output

A list of all values that appear exactly twice, in any order.

Example 1

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

Output: [2, 3]

2 and 3 each appear twice. Every other value appears once.

Example 2

Input: nums = [1, 1, 2]

Output: [1]

1 appears twice.

Example 3

Input: nums = [1]

Output: []

Nothing repeats, so the answer is empty.

Constraints

• n == nums.length
• 1 ≤ n ≤ 10^5
• 1 ≤ nums[i] ≤ n
• Each value appears once or twice.
• O(N) time and O(1) extra space (not counting the output).

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The values are 1..n and the array has n slots. Is there a natural slot for each value?
2.
If I had unlimited memory, how would I notice that I am seeing a value for the second time?
3.
If two copies of the same value both want the same slot, what happens to the second one?
4.
When I move a value to its slot, where does the old resident go?
5.
When should I stop swapping at a position so the loop cannot run forever?

Brute force approach

Idea

Check every pair (i, j) with i < j. If nums[i] == nums[j], that value is a duplicate. Since a value appears at most twice, each duplicate makes exactly one equal pair, so nothing is reported twice.

Thinking process

1
"Appears twice" means there are two positions holding the same value.
2
So the most direct check is: for every position, is there another position with the same value?
3
Only look to the right (j > i). Then the pair is found once, from its left copy.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<int> result;

        // Compare every pair (i, j) with i < j.
        // A value appears at most twice, so each duplicate forms exactly one equal pair.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    result.push_back(nums[i]);
                    break;          // nums[i] has no third copy to find
                }
            }
        }
        return result;
    }
};

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    result.add(nums[i]);
                    break;
                }
            }
        }
        return result;
    }
}

class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result: list[int] = []
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    result.append(nums[i])
                    break
        return result

export function findDuplicates(nums: number[], ...args: any[]): number[] {
    const n = nums.length;
    const result: number[] = [];
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] === nums[j]) {
                result.push(nums[i]);
                break;
            }
        }
    }
    return result;
}

Complexity

Time O(N²)Space O(1)

About n²/2 comparisons. With n = 10^5 that is 5·10^9 — far too slow.

Better approach

Why brute force is slow

For every position, brute force scans the rest of the array to find a twin.

What repeated work are we doing?

The same elements are compared again and again, once for every position to their left.

What information can we reuse?

Remember each value the first time you see it, in count[value]. The second sighting is then one O(1) lookup.

New approach

Idea

Values are 1..n, so count[v] can live in a plain array. Walk once; when count[x] becomes 2, x is a duplicate.

Thinking process

1
The brute force rescans the array to ask "have I seen this value before?"
2
That is a memory question. Remember what we have seen instead of searching for it.
3
The values are small (1..n), so a vector indexed by value works — no hash map needed.

Code & Implementation

better.cpp

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<int> result;

        // Values are 1..n, so a plain array of size n + 1 can count them.
        vector<int> count(n + 1, 0);
        for (int x : nums) {
            count[x]++;
            if (count[x] == 2) result.push_back(x);   // second sighting = duplicate
        }
        return result;
    }
};

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<Integer> result = new ArrayList<>();
        int[] count = new int[n + 1];
        for (int x : nums) {
            count[x]++;
            if (count[x] == 2) result.add(x);
        }
        return result;
    }
}

class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result: list[int] = []
        count = [0] * (n + 1)
        for x in nums:
            count[x] += 1
            if count[x] == 2:
                result.append(x)
        return result

export function findDuplicates(nums: number[], ...args: any[]): number[] {
    const n = nums.length;
    const result: number[] = [];
    const count = new Array(n + 1).fill(0);
    for (const x of nums) {
        count[x]++;
        if (count[x] === 2) result.push(x);
    }
    return result;
}

Complexity

Time O(N)Space O(N)

Fast, but the count array is n + 1 extra integers. The problem asks for O(1) extra space.

Optimized approach

Idea

Start from brute force

The better version keeps count[v] in an extra array of size n + 1 and reports v when its count reaches 2.

Find the repeated work

Nothing is recomputed any more — the problem is the memory. But the count array is indexed by 1..n, and the input has exactly n slots. So the input can hold the same information: slot v − 1 holding v means "I have seen v".

Define the state — what variables do I need?

i: The slot we are fixing now. We keep swapping until nums[i] cannot move.
v = nums[i]: The value sitting at i. Its home is index v − 1.
nums[v − 1]: What is in v's home right now. If it already equals v, v cannot go there.

Define validity

Keep swapping nums[i] home while nums[i] != nums[nums[i] − 1]. After that, every index with nums[i] != i + 1 holds a duplicate value.

Define the transitions — when does each pointer move, and why is it safe?

nums[nums[i] − 1] != nums[i]

swap(nums[i], nums[nums[i] − 1]) and look at nums[i] again

The value lands in its home and never moves again. The value that came back to i may also belong somewhere else, so we check it next.

nums[i] == i + 1

move to i + 1

This value is already home. Nothing to do.

nums[i] != i + 1 but nums[nums[i] − 1] == nums[i]

leave it, move to i + 1

Its home is held by its twin. Swapping two equal values changes nothing, so it would loop forever. This copy is a squatter — remember, it is a duplicate.

After placement

for each i with nums[i] != i + 1, add nums[i] to the answer

A value that appears once always reaches its home. Only the second copy of a duplicated value is left out of place.

What does the current window add to the answer?

Each swap fixes one slot for good. The final scan reads every out-of-place value; each one is the extra copy of a duplicated value, and each duplicated value has exactly one extra copy, so each answer is reported once.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();

        // Cyclic sort: value v belongs at index v - 1.
        for (int i = 0; i < n; i++) {
            // Stop when nums[i]'s home already holds that value:
            // either nums[i] is home, or its twin got there first.
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        // Every value that is not at its home is a "squatter":
        // its home is taken by its twin, so it is a duplicate.
        vector<int> result;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) result.push_back(nums[i]);
        }
        return result;
    }
};

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] != nums[nums[i] - 1]) {
                int target = nums[i] - 1;
                int temp = nums[target];
                nums[target] = nums[i];
                nums[i] = temp;
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) result.add(nums[i]);
        }
        return result;
    }
}

class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        n = len(nums)
        for i in range(n):
            while nums[i] != nums[nums[i] - 1]:
                target = nums[i] - 1
                nums[i], nums[target] = nums[target], nums[i]
        return [nums[i] for i in range(n) if nums[i] != i + 1]

export function findDuplicates(nums: number[], ...args: any[]): number[] {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] !== nums[nums[i] - 1]) {
            const target = nums[i] - 1;
            const temp = nums[target];
            nums[target] = nums[i];
            nums[i] = temp;
        }
    }
    const result: number[] = [];
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) result.push(nums[i]);
    }
    return result;
}

Complexity

Time O(N)Space O(1)

The while inside the for looks like O(N²), but every swap puts one value into its home for good. So there are at most n swaps in total. The array is rearranged in place.

Equal alternative — sign marking: for each x = |nums[i]|, look at nums[x − 1]. If it is already negative, x was seen before, so add x to the answer; otherwise make it negative. Also O(N) time and O(1) space, and it never moves values. It is the main tool in the next question.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each i, look for an equal value at some j > i	O(N²)	O(1)
Better	Count each value in an array of size n + 1; report at count 2	O(N)	O(N)
Optimal	Swap each value v home to index v − 1; values not at home are duplicates	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“values between 1 and n”Each value has a home index v − 1 inside the array.
“appears once or twice”At most one extra copy per value — it will be the one left out of place.
“O(1) extra space”No count array or hash set — the input must store "seen" itself.
“return all duplicates”Read the answer off every misplaced slot, not just the first one.

values in 1..n+find what repeats+O(1) extra space→Cyclic Sort — Duplicate number (squatters after placement)

This is the anchor of the duplicate sub-pattern. In the missing sub-pattern you read the index of a bad slot (i + 1 is missing). Here you read the value in the bad slot (nums[i] is a duplicate). It is the same placement loop; only what you collect afterwards changes. The stop condition must compare with the home's value, because the twin may already be sitting there.

Don't make this mistake

Stopping on the wrong condition (infinite loop)

✗ while (nums[i] != i + 1) swap(nums[i], nums[nums[i] - 1]);

✓ while (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);

This is the pattern-confusion trap from plain cyclic sort, where every value is distinct. Here a value can repeat. On [1, 1], at i = 1 the value 1 is not at index 1, so the wrong loop swaps it with index 0 — which also holds 1. Nothing changes and the loop never ends. Check the home's value instead.

Reporting the index instead of the value

✗ if (nums[i] != i + 1) result.push_back(i + 1);

✓ if (nums[i] != i + 1) result.push_back(nums[i]);

i + 1 is the value missing from the array (that is the Find All Numbers Disappeared question). The value sitting in the bad slot is the duplicate.

Using if instead of while

✗ if (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);

✓ while (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);

After one swap, the value that lands at i may also need to move. On [4, 3, 2, 7, 8, 2, 3, 1] a single swap per index ends with [7, 2, 3, 4, 1, 2, 3, 8] and reports [7, 1, 2, 3] instead of [2, 3].

Sorting or a hash set

✗ sort(nums.begin(), nums.end()); // O(N log N) // or unordered_map<int, int> cnt; // O(N) space

Both find the duplicates, and the judge may accept them, but they break the stated limits. The values being 1..n is the signal that the array can be its own count array.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Cyclic Sort translate into production architectures and low-level memory mechanics.

LLD Architecture