Find The Duplicate Number

The problem

nums holds n + 1 whole numbers, each between 1 and n. Exactly one value appears more than once. It may appear twice or more often, so some of the other values from 1 to n may be missing. Return the value that repeats. You may not change nums, and apart from nums you may use only a constant amount of memory, however long the list is.

What to write

function solve(nums: number[]): number

Input
nums = [1,3,4,2,2]

Output
2

Input
nums = [3,1,3,4,2]

Output
3

Constraints

Find it without changing the array and using constant extra space.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   With n + 1 entries and only n allowed values, a repeat is certain. Sorting would change the list, and a set of the values seen grows with the list, so both usual tools are forbidden. Look at the limits instead: every value is between 1 and n, so every value is also a valid index.

2. Hint 2: Ask a smaller question

   Every value in 1, 3, 4, 2, 2 is also an index of the list. Start at index 0, read the value there, go to the index with that number, and repeat. Write down the indexes you visit. What do you notice after a few jumps, and which index is the first to come up twice?

3. Hint 3: Name the pattern

   Reading each value as the index to visit next turns the list into a chain, like a linked list whose links are the values. The chain never ends, so it runs into a cycle, and the index where the cycle begins is the repeated value. A hidden linked list with a cycle signals fast and slow pointers. Read the lesson on fast and slow pointers.

4. Hint 4: State the invariant

   When the two pointers first meet, the fast pointer has made twice as many jumps as the slow one and is on the same index. So the slow one's jump count is a whole number of laps. After that, a pointer that starts over and one left at the meeting place arrive where the cycle begins on the same jump.

5. Hint 5: Sketch the pseudocode

   A jump replaces a number with the value stored at that index. slow and fast both start as the value at index 0. Repeat: slow jumps once and fast jumps twice, until they are equal. Put slow back on the value at index 0. While they differ, both jump once. Return slow.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Interpret each array value as a next pointer. The duplicate is the entry of the resulting cycle, found with Floyd’s two-phase algorithm.

The slow way

Take each entry in turn and scan the entries after it for an equal value. That obeys both rules, because it changes nothing and stores almost nothing, but it compares every pair of entries: about n × n / 2 comparisons. The quicker ideas, sorting the list or keeping a set of the values seen, break the rules.

The insight

Every value is between 1 and n, so every value is also a valid index. Read each value as "go to this index next", starting from index 0. The walk can never stop, so it runs into a cycle: a stretch of indexes it repeats for ever. The index where the walk enters the cycle is reached from two different indexes, so its number is stored twice.

Step by step

1. Start a slow and a fast pointer on the value stored at index 0. Each pointer is a number that is used as an index. No value is 0, so nothing ever jumps back to index 0: the walk starts there, and the value stored there is its first stop.
2. Jump the slow pointer once and the fast one twice until they meet. A jump replaces a pointer with the value stored at the index it holds. The walk runs into a cycle, and inside it the faster pointer catches the slower one. Compare only after jumping, because both start equal.
3. Send the slow pointer back to the value stored at index 0. The meeting place is somewhere inside the cycle, not necessarily where the cycle begins. A second walk finds the beginning: one pointer starts over and the other stays at the meeting place.
4. Jump both pointers once at a time until they meet again. The slow pointer's jumps before the first meeting add up to a whole number of laps. So the pointer that starts over and the pointer inside the cycle arrive where the cycle begins on the same jump.
5. The value they meet on is the one that repeats. They meet where the walk enters the cycle. That index is reached from two different indexes, one outside the cycle and one inside, so the number of that index is stored at both.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Start a slow and a fast pointer on the value stored at index 0
  let slow = nums[0],
    fast = nums[0];
  // 2. Jump the slow pointer once and the fast one twice until they meet
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);
  // 3. Send the slow pointer back to the value stored at index 0
  slow = nums[0];
  // 4. Jump both pointers once at a time until they meet again
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  // 5. The value they meet on is the one that repeats
  return slow;
}

function solve(nums: number[]): number {
  // 1. Start a slow and a fast pointer on the value stored at index 0
  let slow = nums[0],
    fast = nums[0];
  // 2. Jump the slow pointer once and the fast one twice until they meet
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);
  // 3. Send the slow pointer back to the value stored at index 0
  slow = nums[0];
  // 4. Jump both pointers once at a time until they meet again
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  // 5. The value they meet on is the one that repeats
  return slow;
}

def solve(nums):
    # 1. Start a slow and a fast pointer on the value stored at index 0
    slow = fast = nums[0]
    # 2. Jump the slow pointer once and the fast one twice until they meet
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # 3. Send the slow pointer back to the value stored at index 0
    slow = nums[0]
    # 4. Jump both pointers once at a time until they meet again
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    # 5. The value they meet on is the one that repeats
    return slow

Example 1, traced

Input
nums = [1,3,4,2,2]

Output
2

Why it works

The walk from index 0 must enter a cycle. The index where the walk enters is stored at two indexes, so that index is the repeated value. At the first meeting the fast pointer has made twice the slow one's jumps, so the slow one's jumps are whole laps. So a pointer that starts over and one at the meeting place reach the entry index on the same jump.

Time and space

Time O(n), extra space O(1). The first loop ends within n jumps of the slow pointer and the second loop within n more, so the time is O(n). The list is only read, never changed, and two numbers are all that is stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not return the place where the pointers first meet. It is only somewhere in the cycle. For 1, 2, 3, 4, 2 they first meet on 4, but the repeated value is 2.
• Send the slow pointer back to the value at index 0, the place where both pointers began. Restarting it on index 0 itself leaves the two pointers out of step, and on the first example they never meet.
• In the first loop, compare only after jumping. Both pointers start on the same value, so a comparison made first ends the loop at once, and the first example returns 1, the value at index 0.

Pattern

Fast and slow pointers. Builds on Linked List Cycle.

Keep going