Find all Duplicate Numbers (Every Value Appearing Twice in 1..n)

• Problem – n integers in range 1..n; some appear once, some twice. Return all that appear twice in O(n) time and O(1) space.
• Cyclic Sort – place each value v at index v-1 with a value-comparison guard to prevent infinite swaps.
• Stranded values – after placement, any slot where value != index+1 holds a duplicate that was pushed out of its home.
• Dual property – on the same sorted array, scanning for index+1 gives missing numbers; scanning for stored value gives duplicates.
• Alternative – negative marking flips the sign at index abs(v)-1; a second flip reports the duplicate.

What is the Find All Duplicates problem?

Given an array of n integers where each value is in the range 1 to n, some values appear once and some appear exactly twice. Return all the values that appear twice. The constraint is O(n) time and O(1) extra space (the output list is excluded from the space count).

package com.bank.dsa;

import java.util.List;

public interface DuplicateFinder {
    List<Integer> findDuplicates(int[] nums);
}

How does the Cyclic Sort approach work?

Run the standard Cyclic Sort placement loop, but with a value-comparison guard: while nums[i] != nums[nums[i] - 1], swap nums[i] with nums[nums[i] - 1]. The guard prevents infinite swaps when a duplicate is encountered (both positions hold the same value, so further swapping is pointless).

After placement, scan the array. Any slot where nums[i] != i + 1 holds a stranded duplicate value. Collect those values.

package com.bank.dsa;

import java.util.*;

public class ReceiptAuditor {
    public static List<Integer> findDuplicates(int[] receipts) {
        // Cyclic Sort placement
        int i = 0;
        while (i < receipts.length) {
            int home = receipts[i] - 1;
            if (receipts[i] != receipts[home]) {
                int temp = receipts[i];
                receipts[i] = receipts[home];
                receipts[home] = temp;
            } else {
                i++;
            }
        }

        // Collect stranded duplicates
        List<Integer> duplicates = new ArrayList<>();
        for (int j = 0; j < receipts.length; j++) {
            if (receipts[j] != j + 1) {
                duplicates.add(receipts[j]);
            }
        }
        return duplicates;
    }

    public static void main(String[] args) {
        int[] receipts = {4, 3, 2, 7, 8, 2, 3, 1};
        System.out.println("Duplicates: " + findDuplicates(receipts));
    }
}

Duplicates: [2, 3]

How does the negative-marking approach work?

For each value v, compute index = abs(v) - 1. If the element at that index is already negative, v is a duplicate (the index was already visited). Otherwise negate the element at that index. This uses the sign bit as a visited flag.

package com.bank.dsa;

import java.util.*;

public class NegativeMarkingDuplicates {
    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int num : nums) {
            int idx = Math.abs(num) - 1;
            if (nums[idx] < 0) {
                result.add(Math.abs(num));
            } else {
                nums[idx] = -nums[idx];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
        System.out.println("Duplicates: " + findDuplicates(nums));
    }
}

Duplicates: [2, 3]

What is the dual property of Cyclic Sort?

On the exact same array after Cyclic Sort, scanning for i + 1 gives the missing numbers (the values that never made it home), while scanning for nums[i] gives the duplicates (the values that were stranded). This elegant duality is why Cyclic Sort is the preferred approach for both the find-missing and find-duplicates problems.

// After Cyclic Sort: [1, 2, 3, 4, 3, 2, 7, 8]
// Slot 4: nums[4]=3, 3 != 5 --> duplicate is 3, missing is 5
// Slot 5: nums[5]=2, 2 != 6 --> duplicate is 2, missing is 6

// Collect duplicates: scan for nums[i]
// Collect missing:    scan for i + 1

How is this different from Find the Duplicate Number (single)?

Find the Duplicate Number has n+1 elements and exactly one duplicate. Find All Duplicates has n elements and potentially multiple duplicates. The single-duplicate variant can use Floyd's cycle detection (read-only), while find-all-duplicates requires Cyclic Sort or negative marking (both mutate).

| Problem | Array Size | Duplicates | Best Approach |
|---|---|---|---|
| Find the Duplicate | n+1 | Exactly one | Floyd's (read-only) or Cyclic Sort |
| Find All Duplicates | n | Zero or more | Cyclic Sort or negative marking |

What are edge cases?

Edge cases include no duplicates (every value appears once, return empty), all duplicates (every pair appears, return n/2 values), and a single element (return empty since it can only appear once).

findDuplicates(new int[]{1, 2, 3});     // []
findDuplicates(new int[]{1, 1, 2, 2});  // [1, 2]
findDuplicates(new int[]{1});           // []

What are common mistakes?

The most common mistake with Cyclic Sort is using an index-comparison guard (nums[i] != i + 1) instead of a value-comparison guard (nums[i] != nums[home]), which causes infinite swaps when a duplicate is at its home index. Another is collecting i + 1 instead of nums[i] in the scan, which gives missing numbers instead of duplicates.

// Wrong: collecting i+1 gives missing numbers
if (nums[i] != i + 1) result.add(i + 1); // missing, not duplicate

// Correct: collecting nums[i] gives duplicates
if (nums[i] != i + 1) result.add(nums[i]); // duplicate

What should a senior engineer know?

A senior engineer explains the dual property of Cyclic Sort (duplicates vs missing from the same placement), knows both the Cyclic Sort and negative-marking approaches, and picks based on readability. They note that negative marking cannot answer the missing-numbers question in the same pass, while Cyclic Sort can answer both.