You are given an array of integers where:

• all numbers are in the range 1 to n
• n is the size of the array
• some elements appear once, some twice

Your task:
Return all elements that appear exactly twice in the array, without using extra space proportional to n.

Example:

Input:  [4,3,2,7,8,2,3,1]
Output: [2,3]

---

Problem Requirements and Constraints

• Array length n where 1 ≤ nums[i] ≤ n
• You must return duplicates
• Order of output does not matter
• Time complexity should be O(n)
• Extra space must be O(1) (output list does not count)

This means:

• No HashSet
• No frequency arrays
• No sorting that costs extra space

---

Logic Explained

The key insight:

Since all numbers are between 1 and n, each number corresponds to a valid index in the array when we subtract 1.

Example:
Number 4 corresponds to index 3
Number 1 corresponds to index 0
Number 7 corresponds to index 6

So here is the trick:

1. Walk through the array
2. For each number, map it to its index (abs(num) – 1)
3. Look at the value at that index
4. If it is positive, flip it to negative
   • meaning “we have seen this number once”
5. If it is already negative, it means:
   • we have seen this number before
     → so it is a duplicate

Why this works:

• Flipping the sign allows the array itself to store visit information
• A second visit indicates duplication

No extra storage needed.

---

Step-by-Step Approach

1. Initialize an empty result list
2. Loop through each number in the array
3. Convert it to an index using abs(num) – 1
4. Check nums[index]
   • If positive → flip sign
   • If negative → add abs(num) to result list
5. Return result list

This satisfies:

• O(n) time
• O(1) space (ignoring result)

---

Java Implementation

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();

        for (int num : nums) {
            int index = Math.abs(num) - 1;

            if (nums[index] < 0) {
                result.add(Math.abs(num));
            } else {
                nums[index] = -nums[index];
            }
        }

        return result;
    }
}

---

Dry Run Example

Input:

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

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

Step 1: num = 4

index = 3
nums[3] = 7 (positive) → flip
nums = [4,3,2,-7,8,2,3,1]

Step 2: num = 3

index = 2
nums[2] = 2 (positive) → flip
nums = [4,3,-2,-7,8,2,3,1]

Step 3: num = -2

index = 1
nums[1] = 3 (positive) → flip
nums = [4,-3,-2,-7,8,2,3,1]

Step 4: num = -7

index = 6
nums[6] = 3 (positive) → flip
nums = [4,-3,-2,-7,8,2,-3,1]

Step 5: num = 8

index = 7
nums[7] = 1 (positive) → flip
nums = [4,-3,-2,-7,8,2,-3,-1]

Step 6: num = 2

index = 1
nums[1] = -3 (negative) → duplicate
result = [2]

Step 7: num = -3

index = 2
nums[2] = -2 (negative) → duplicate
result = [2, 3]

Step 8: num = -1

index = 0
nums[0] = 4 (positive) → flip
nums = [-4,-3,-2,-7,8,2,-3,-1]

Final result:

[2, 3]

---

Time and Space Complexity

Time Complexity

O(n) — one scan through array

Space Complexity

O(1) — modification happens in-place
(result list does not count)

---

Common Mistakes and How to Avoid Them

Mistake 1: Using HashSet or frequency array

This violates space constraints.

Mistake 2: Sorting the array

Sorting costs O(n log n) and may modify input improperly.

Mistake 3: Forgetting to use absolute value

Negative values can break index mapping if not handled.

Mistake 4: Returning duplicates multiple times

Only add when encountering the negative state.

Mistake 5: Trying to restore the array unnecessarily

Restoration is not required unless the interviewer asks.