List Every Number That Appears Twice

Given an array nums of length n where every value is between 1 and n, and each value appears either once or twice, return every value that appears twice. The array's own values are secretly valid indices into itself — that's the constraint a brute-force scan throws away. Treat each value as a pointer to a slot, and flip the sign of what's stored there the first time you visit it. A negative sign IS the "already seen" flag, so a second visit to the same slot is instantly recognizable — no hash set required, and the whole scan finishes in a single O(n) pass.

Test Case 1:

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

Output:[2, 3]

Explanation:2 and 3 are the only values appearing twice. Order doesn't matter.

Test Case 2:

Input:nums = [1, 1, 2]

Output:[1]

Explanation:Only 1 repeats.

Test Case 3:

Input:nums = [1]

Output:[]

Explanation:No value repeats.

Constraints

◆1 ≤ n = nums.length ≤ 10⁵
◆1 ≤ nums[i] ≤ n
◆Each integer appears once or twice — never more

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-9 values, each 1..n, at most twice each

1	class Solution {
2	public int[] findAllDuplicates(int[] nums) {
3	List<Integer> result = new ArrayList<>();
4	for (int i = 0; i < nums.length; i++) {
5	int index = Math.abs(nums[i]) - 1;
6	if (nums[index] < 0) {
7	result.add(index + 1);
8	} else {
9	nums[index] = -nums[index];
10	}
11	}
12	int[] arr = new int[result.size()];
13	for (int i = 0; i < arr.length; i++) arr[i] = result.get(i);
14	return arr;
15	}
16	}
17

4

3

2

7

8

2

3

1

0

1

2

3

4

5

6

7

Variables

result[]

INITIALIZE

Start with an empty result. We'll reuse the array itself to remember which values we've already seen, by flipping their sign.

Step 1 / 26

Approach & Solutions

Brute Force

Brute

For every value, rescan the whole array to count how many times it appears. If it appears exactly twice and hasn't already been recorded, add it to the result. Correct, but re-counting from scratch for every position wastes the fact that the array only needs a single pass to answer this.

TimeO(n²)

SpaceO(1) extra

Java

Try it out

class Solution {
    public int[] findAllDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == nums[i]) count++;
            }
            if (count == 2 && !result.contains(nums[i])) {
                result.add(nums[i]);
            }
        }
        int[] arr = new int[result.size()];
        for (int i = 0; i < arr.length; i++) arr[i] = result.get(i);
        return arr;
    }
}

Optimal — Negative Marking In-Place

Optimal

Every value in this array is guaranteed to be a valid 1-based index into the same array — that constraint is the key to an O(1)-space trick. Walk the array once: for each value, look at the slot it points to (its absolute value minus one). If that slot's number is already negative, this value has been seen before — it's a duplicate. Otherwise, negate the number in that slot to mark "seen." The array's own sign bits become the hash set, with no extra memory needed.

TimeO(n)