Find All Duplicates in an Array of 1 to N

Title: Find All Duplicates in an Array of 1 to N

Finding every value that repeats inside an array whose elements are drawn from the range 1 to n is a favorite interview problem, because the tight constraint on the values unlocks a clever constant-extra-space solution. In this guide, you will learn how to spot duplicates by flipping the sign of array positions, write a complete Java implementation, trace the algorithm one iteration at a time, and sharpen your intuition with worked examples, common mistakes, and the follow-up questions interviewers like to drill into.

Understanding the Problem

You are given an integer array nums of length n where every element lies in the inclusive range [1, n]. Each value appears either once or twice. Return a list of all values that appear exactly twice.

For instance, if nums = {4, 3, 2, 7, 8, 2, 3, 1}, the answer is [2, 3] because those two values each occur twice while the rest occur once. The order of the returned list does not have to match any particular convention; most interviewers accept any permutation of the correct answer.

The interesting constraint is the value range: every element is a valid array index after you subtract one. That mapping is what lets us turn each position of the input into a lightweight bookmark and solve the problem without an auxiliary hash table.

Approach Using Sign Flipping

The key observation is that each value v can be mapped to a target index v - 1. The first time we see v, we mark its target position by negating the number stored there. The second time we see v, its target position is already negative, so we recognize the repeat and add v to the result. The absolute value of nums[i] is always used when reading, so the sign only acts as a boolean flag without destroying the value information we still need.

Here are the steps:

1. Create an empty List<Integer> called result.
2. Iterate the index i from 0 to nums.length - 1.
3. Read the current value as value = Math.abs(nums[i]) so the flag bit does not pollute arithmetic.
4. Compute index = value - 1, the slot that represents value.
5. If nums[index] < 0, value has been seen before; append value to result.
6. Otherwise, flip the sign: nums[index] = -nums[index] to mark value as seen.
7. Return result after the loop finishes.

Java Program to Find All Duplicates in an Array of 1 to N

Let us put the approach into a complete, compilable Java program:

import java.util.ArrayList;
import java.util.List;

public class FindAllDuplicates {

    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int value = Math.abs(nums[i]);
            int index = value - 1;
            if (nums[index] < 0) {
                result.add(value);
            } else {
                nums[index] = -nums[index];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
        List<Integer> duplicates = findDuplicates(nums);
        System.out.println("Duplicate values: " + duplicates);
    }
}

Explanation of the Program

• The method findDuplicates accepts an int[] and returns a List<Integer> holding every value that appears exactly twice.
• result is an ArrayList because we collect duplicates in insertion order and only ever append. We never need random removal, so the simplest list type is a good fit.
• Math.abs(nums[i]) peels off the sign before the value is used as a pointer. Without this call, the mark we leave on a prior iteration would corrupt the very index we are trying to compute.
• index = value - 1 converts a one-based value into a zero-based array offset. Pairing it with the constraint 1 <= nums[i] <= n is what makes every element a valid pointer into the array.
• The if branch handles the second sighting: a negative mark at nums[index] means value has already been seen, so we add it to result.
• The else branch handles the first sighting: we negate nums[index] so a later iteration can detect the duplicate.
• main calls the method on a sample input and prints the duplicates. The sample is the canonical LeetCode example, which makes it easy to compare the output to published solutions.

Step-by-Step Trace

Let us walk the algorithm through a small fresh input so the sign flipping is easy to follow. Consider nums = {2, 5, 1, 5, 3, 2} with length 6; result starts empty.

At the end of iteration i, the slot at Math.abs(v) - 1 is negative for every value v we have already seen in nums[0..i]. That invariant is what lets a single pass separate first sightings from repeats, and result ends holding [5, 2] without needing any extra data structure beyond the output list itself.

Examples

Let us look at a few runs that stretch different parts of the algorithm.

Example 1: The Canonical Interview Input

int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
List<Integer> duplicates = findDuplicates(nums);

System.out.println("Duplicates: " + duplicates);
// Output: Duplicates: [2, 3]

The array has eight elements. 2 and 3 appear twice, while 1, 4, 7, and 8 appear once. The method returns [2, 3], which is the published answer on LeetCode.

Example 2: Duplicate at the Start

int[] nums = {1, 1, 2};
List<Integer> duplicates = findDuplicates(nums);

System.out.println("Duplicates: " + duplicates);
// Output: Duplicates: [1]

The first two elements are both 1. On i = 0 the slot nums[0] is flipped to -1; on i = 1 we read Math.abs(-1) = 1 again, find nums[0] already negative, and append 1 to the result. Short inputs still rely on the exact same loop.

Example 3: Every Value is Distinct

int[] nums = {1, 2, 3, 4, 5};
List<Integer> duplicates = findDuplicates(nums);

System.out.println("Duplicates: " + duplicates);
// Output: Duplicates: []

No value repeats, so every slot gets flipped exactly once and no index is visited twice. The returned list is empty, which is the expected answer when the array is a permutation of [1, n].

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing the sign-flip trick:

• Forgetting Math.abs when reading the value – using int value = nums[i] directly on a slot you have already flipped feeds a negative number into value - 1, which crashes with ArrayIndexOutOfBoundsException. Always strip the sign first with Math.abs.
• Indexing by value instead of value – 1 – skipping the subtraction overflows the array for value == n and misses the slot 0 entirely for value == 1. The slot that represents v is v - 1, not v.
• Adding the index to the result instead of the value – returning index gives the zero-based position, so {1, 1, 2} would report 0 instead of 1. Append value, which is the actual integer the caller asked about.
• Reusing the mutated input as if it were untouched – the array is left with negative entries after the pass, so a caller that later prints nums sees garbage. If the caller still needs the original data, copy the array first or restore the signs in a cleanup pass.
• Mishandling the empty array – returning null for nums.length == 0 forces every caller to add a null check. Return an empty list instead; the loop naturally yields that answer.

Additional Considerations

A few points worth remembering about this algorithm:

1. Time complexity: One pass over n elements performs a constant amount of work per iteration, so the total running time is O(n).
2. Space complexity: Beyond the result list, no auxiliary data structure is used. The extra space is O(1) when the output list is excluded, which is why this problem shows up when interviewers want to test in-place thinking.
3. Input mutation: The sign-flip trick writes to the input array. In production code that is a side effect worth documenting; if the caller must preserve nums, run a second pass to flip every negative entry back to positive.
4. Why the value range matters: The guarantee 1 <= nums[i] <= n is what lets each value point to a valid index. Drop that constraint and the trick falls apart; a HashSet becomes the natural replacement.
5. Alternative with a HashSet: Add each value to a Set<Integer> and move it to the result when the add returns false. The complexity becomes O(n) time and O(n) extra space, but the input stays untouched.

Edge Cases to Test

Before you declare the implementation done, run it against these boundary inputs:

• Empty array
• Single-element array
• No duplicates (a permutation of 1 to n)
• Every eligible value duplicated
• Duplicate pair at the first two positions
• Duplicate pair at the last two positions
• Value 1 and value n both duplicated
• Null array reference

Interview Follow-up Questions

Once the base version works, an interviewer will usually probe deeper with questions like these:

• What if you cannot mutate the input array? – fall back to a HashSet<Integer> or a boolean seen array of length n + 1; both keep the input intact at the cost of O(n) extra space.
• How would you also report the missing values in the range 1 to n? – after the sign-flip pass, any index i whose nums[i] is still positive corresponds to the missing value i + 1; collect those indices in a second scan.
• What if elements can appear three or more times? – sign flipping no longer encodes the count, so switch to a frequency map (HashMap<Integer, Integer>) and report every key whose count is at least two.
• What if the input arrives as a stream whose length is unknown? – a HashSet is the natural choice because you cannot index back into a stream; emit each value the first time you see it a second time.
• How would you handle billions of entries that will not fit in memory? – shard the input by value range, process each shard independently on a worker, and union the per-shard duplicate lists; approximate alternatives include a Bloom filter or a count-min sketch when a small false-positive rate is acceptable.

Conclusion

In this guide, we solved the problem of finding every repeating value in an array whose elements lie in the range 1 to n. The sign-flip trick turns each slot into a lightweight bookmark, letting findDuplicates collect every repeat in a single pass with O(n) time and O(1) extra space beyond the output list. That combination is why the problem is such a staple in coding interviews; it rewards candidates who read the constraints closely.

Try adapting the code to report the missing values alongside the duplicates, restore the input array before returning, or swap the sign flipping for a HashSet when you cannot mutate the input. Happy coding!

You can learn more about Array techniques: Arrays