Find duplicate in an array of N+1 Integers

The problem, simply

You get an array with n + 1 numbers, and every number is between 1 and n. There are more numbers than possible values, so at least one value must repeat. Exactly one value repeats (it may repeat more than twice). Find it.

The hard rules: do not change the array, and use only a few extra variables.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a checklist of the numbers you have seen. The first number that is already ticked is the repeat.

1. Make a seen array of size n + 1, all false.
2. For each number x: if seen[x] is true, return x. Otherwise set it to true.

class Solution {
    public int findDuplicate(int[] nums) {
        boolean[] seen = new boolean[nums.length];   // values go from 1 to n
        for (int x : nums) {
            if (seen[x]) return x;                    // ticked already: the repeat
            seen[x] = true;
        }
        return -1;                                    // cannot happen for valid input
    }
}

How long it takes: one walk, O(n). Extra room: the checklist, O(n). That breaks the "few extra variables" rule. Sorting first would also find it, but sorting changes the array.

Way 2: the clever way

Treat the array as a chain of boxes: box k has an arrow to box nums[k]. The repeated value is a box with two arrows coming in, and that is exactly where the chain starts to loop. So the repeat is the entrance of the loop, and we can find it with two runners (Floyd's cycle finding).

1. Phase 1: slow moves one arrow at a time, fast moves two. Run until they stand on the same box. That box is somewhere inside the loop.
2. Phase 2: put slow back at the start. Move both one arrow at a time. Where they meet is the loop's entrance, the duplicate.

Why phase 2 works: say the path before the loop is a steps and the meeting box is b steps into the loop. Fast walked twice as far as slow, and the extra distance a + b is a whole number of laps. So walking a more steps from the meeting box finishes a lap and lands on the entrance, and a runner from the start reaches the entrance after the same a steps.

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[0];   // both take their first step from box 0
        do {
            slow = nums[slow];                 // one step
            fast = nums[nums[fast]];           // two steps
        } while (slow != fast);                // they meet inside the loop

        slow = nums[0];                        // back to the start
        while (slow != fast) {
            slow = nums[slow];                 // both walk one step now
            fast = nums[fast];
        }
        return slow;                           // the entrance of the loop
    }
}

How long it takes: both phases take a number of steps that is at most a few times n, so O(n). Extra room: two numbers, O(1). The array is only read, never changed.

Another way: count and halve

This one is easier to come up with in an interview and also keeps the array untouched. Guess a middle value mid. Count how many numbers are <= mid. With no repeat in 1..mid there would be at most mid of them. If there are more, the repeat is in 1..mid; otherwise it is in mid + 1..n. Halve the range of values each time.

class Solution {
    public int findDuplicate(int[] nums) {
        int lo = 1, hi = nums.length - 1;     // the repeat is a value in 1..n
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for (int x : nums) if (x <= mid) count++;
            if (count > mid) hi = mid;        // too many small numbers: repeat is small
            else lo = mid + 1;
        }
        return lo;
    }
}

It takes O(n log n) time and O(1) extra room.

Watch out for

• A plain while (slow != fast) for phase 1 never runs, because both start equal. Use do ... while, or start fast one step ahead.
• Start both phases from the same place. Here both start from nums[0]. Mixing "start at index 0" in one phase with "start at nums[0]" in the other is off by one.
• Marking boxes negative or swapping numbers into place also find the repeat in O(n), but they change the array, which the problem forbids.

What interviewers ask next

• Why must there be a loop? Every box has an arrow out, and there are finitely many boxes, so walking forever must revisit one. Box 0 has no arrow in, so it is not in the loop.
• Why is the entrance the duplicate? The entrance has one arrow from the path and one from inside the loop. Two arrows into box v means two positions hold the value v.
• What if the array may be changed? Swap each number to its home position (cyclic sort) or flip signs to mark seen values. O(n) time, O(1) extra room.
• Find all repeats in an array of size n with values 1..n? Flip the sign at index |x| - 1. A value whose spot is already negative is a repeat.
• Where else is this trick used? Detecting a loop in a linked list and finding where it starts, and the "happy number" problem.

Remember this

Grown-up words: the lockers and notes form a functional graph (a linked list hidden in an array), the circle is a cycle, the two runners are Floyd's tortoise and hare, and "more notes than names" is the pigeonhole principle.