Find All Duplicates in an Array

1. Define the problem

Given an integer array nums of length n where every value is between 1 and n, some values appear once, some appear twice . Find every value that appears twice, using only constant extra space (besides the array used for the output). Since every value doubles as a valid index (value minus one) , walk the array once and flip the sign of the value at that index — landing on an already-negative value means its number has been seen before.

Constraints

n == nums.length
1 ≤ n ≤ 10⁵
1 ≤ nums_i ≤ n
Each element in nums appears once or twice.

Example

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

Output[2, 3]

Explanation Both 2 and 3 appear twice in the array; every other value appears exactly once.

2. Know the words first

In plain terms

Index (value minus one): Because values run from 1 to n but indices run from 0 to n - 1, subtracting 1 from a value gives the matching index to mark.
Flip the sign: Turning a positive number negative as a marker, without losing the original magnitude — Math.abs can always recover it later.

3. Visualize the solution

Flip the sign at each value's index; a negative already there means a duplicate

3-7

Statusmark

i=0, value=4, index=3: nums[3]=7 is positive — mark it by negating: nums[3]=-7.

What happens in this step

value = 4, index = 3
nums[3] = 7 (positive) → negate: nums[3] = -7

Step 1 of 5

Steps to visualize

For each value, compute its matching index (the value minus one).
If the value already stored at that index is negative, this value has been seen before — record it as a duplicate.
Otherwise, flip the sign of the value at that index to mark this value as seen.
After one full pass, every recorded duplicate is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Flip the sign at each value's index; a negative already there means a duplicate

3-7

Statusmark

i=0, value=4, index=3: nums[3]=7 is positive — mark it by negating: nums[3]=-7.

What happens in this step

value = 4, index = 3
nums[3] = 7 (positive) → negate: nums[3] = -7

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function findDuplicates(nums) {
  const duplicates = [];

  for (let i = 0; i < nums.length; i++) {
    const index = Math.abs(nums[i]) - 1;

    if (nums[index] < 0) {
      duplicates.push(index + 1);
    } else {
      nums[index] = -nums[index];
    }
  }

  return duplicates;
}

Time: O(n)
Space: O(1) (excluding the output array)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [4, 3, 2, 7, 8, 2, 3, 1]`	`[2, 3]`	example from the docstring
`nums = [1, 1]`	`[1]`	smallest valid input: a single duplicate pair
`nums = [1, 2, 3, 4]`	`[]`	every value appears exactly once
`nums = [1, 1, 2, 2]`	`[1, 2]`	every value appears exactly twice
`nums = [2, 2, 3, 3, 4, 4]`	`[2, 3, 4]`	several duplicate values mixed with the marking of shared indices
`nums = [3, 1, 3, 4, 2]`	`[3]`	exactly one duplicate hidden among otherwise unique values

Find All Duplicates in an Array