Find All Duplicates in an Array: Index-Marking or Frequency Map

• Frequency map approach – use a HashMap to count occurrences, collecting keys with count >= 2 in O(n) time and O(n) space.
• Index-marking approach – valid when values are in [1, n]; for each value v, negate a[|v| - 1]; if it is already negative, v is a duplicate. O(n) time, O(1) extra space.
• Absolute value – always use Math.abs(a[i]) when computing the target index because the element may have been negated by an earlier visit.
• Array restoration – after collecting duplicates, take absolute values to undo the marks if the caller needs the original array.
• Choice – frequency map for arbitrary values or immutable arrays; index-marking for [1, n] constraint with mutation allowed.

What is the Find All Duplicates problem?

Given an array of integers, report every value that appears more than once. For example, given [4, 3, 2, 7, 8, 2, 3, 1], the duplicates are [2, 3].

In banking, the fraud team at the National Bank of India must detect double-charged transaction reference numbers in a daily batch.

How does the frequency map approach work?

Walk the array once, incrementing each value's count in a HashMap. Collect a value the moment its count reaches exactly two to avoid reporting it multiple times.

package com.bank.fraud;

import java.util.*;

public class DuplicateDetector {

    public static List<String> findDuplicateRefs(String[] refs) {
        Map<String, Integer> freq = new HashMap<>();
        List<String> duplicates = new ArrayList<>();

        for (String ref : refs) {
            int count = freq.merge(ref, 1, Integer::sum);
            if (count == 2) {
                duplicates.add(ref);
            }
        }
        return duplicates;
    }

    public static void main(String[] args) {
        String[] refs = {"TXN001", "TXN002", "TXN003", "TXN001", "TXN004", "TXN002"};
        System.out.println("Duplicate refs: " + findDuplicateRefs(refs));
    }
}

Duplicate refs: [TXN001, TXN002]

How does the index-marking approach work?

• When every value is in the range [1, n] and you may mutate the array, you can use the array itself as the tally sheet. For each value v:
• Compute target index: idx = Math.abs(v) - 1 (values are 1-based, indices are 0-based).
• Check a[idx]: if already negative, v is a duplicate.
• Otherwise, negate a[idx] to mark that v has been seen.

Using Math.abs is essential because the element you read may have been negated by an earlier visit.

package com.bank.fraud;

import java.util.*;

public class IndexMarkingDuplicates {

    public static List<Integer> findDuplicates(int[] batchIds) {
        List<Integer> duplicates = new ArrayList<>();

        for (int i = 0; i < batchIds.length; i++) {
            int idx = Math.abs(batchIds[i]) - 1;
            if (batchIds[idx] < 0) {
                duplicates.add(idx + 1);  // convert back to 1-based
            } else {
                batchIds[idx] = -batchIds[idx];
            }
        }
        return duplicates;
    }

    // Restore array after marking
    public static void restore(int[] batchIds) {
        for (int i = 0; i < batchIds.length; i++) {
            batchIds[i] = Math.abs(batchIds[i]);
        }
    }

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

Duplicates: [2, 3]
Restored: [4, 3, 2, 7, 8, 2, 3, 1]

How is index-marking different from the frequency map?

| Aspect | Frequency Map | Index-Marking |
|---|---|---|
| Value range | Any values | Must be in [1, n] |
| Mutation | Does not mutate input | Negates array elements |
| Extra space | O(n) for the map | O(1) |
| Time | O(n) | O(n) |
| Restoration needed | No | Yes, if caller needs originals |
| Use case | Arbitrary reference strings | Numbered batch IDs |

Why is the absolute value step essential?

When you read a value from the array, it may have been negated by an earlier iteration. Without Math.abs, you would compute a negative index, causing an ArrayIndexOutOfBoundsException. The absolute value recovers the original value for index computation.

// Without abs: if batchIds[2] was negated to -2
int idx = batchIds[2] - 1;  // idx = -3 → ArrayIndexOutOfBoundsException!

// With abs: correctly recovers the value
int idx = Math.abs(batchIds[2]) - 1;  // idx = 1 → correct

What about restoring the array?

Negating elements mutates the input, which may be unacceptable if the caller needs the original values. After collecting duplicates, walk the array and take the absolute value of every element. Silently corrupting a caller's data is a real production bug, so always consider this trade-off.

What are the edge cases?

• No duplicates – the result list is empty.
• All elements the same – every element after the first is a duplicate; with the map approach, the value is collected once at count 2.
• Single element – no duplicates possible.
• Empty array – return an empty list.

When should you use each approach?

Use the frequency map when the value range constraint does not hold, or mutation is forbidden. Use index-marking when the constraint holds and memory is tight, such as processing huge batches. Rajesh at the National Bank of India would choose index-marking for numbered batch IDs to save memory on millions of transactions, but the map for arbitrary reference strings.

What are common interview follow-up questions?

• Can you do it in O(1) space? – Yes, with index-marking if values are in [1, n].
• What if values can appear more than twice? – The map handles any count; marking flags presence only, not exact count.
• What about finding the missing number? – A similar index-marking trick finds the number not present.