Find All Duplicates in an Array

Difficulty: Medium

Problem

Given an integer array nums of length n where all the integers are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appear twice.

Example

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Explanation: 2 and 3 appear twice.

Brute-force approach

For each element, scan the rest of the array to check if it appears again.

Steps

1. For each i, check j > i
2. If nums[i] == nums[j], record nums[i]
3. Avoid adding the same duplicate multiple times

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

• Quadratic time
• Harder to avoid duplicate reporting without extra logic

Optimal approach

Key insight: Use the array itself as a marker. Value x maps to index (x-1). First visit marks negative; second visit detects duplicate.

Two approaches: Hash Set (O(n) space) or In-Place Marking (O(1) space).

Steps

1. For each value, compute target index = |value| - 1
2. If nums[index] is negative, value is a duplicate
3. Otherwise, mark nums[index] as negative

Time complexity: O(n) · Space complexity: O(1)