Find the Duplicate Number

Interview Problem Interview Medium Fast and Slow Pointers Array Cycle Detection

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.findDuplicate(nums). nums has n+1 integers, each in [1,n], and exactly one value appears more than once. Return that value without modifying nums and with O(1) auxiliary space.

Starter code

class Solution:
    def findDuplicate(self, nums):
        pass

Test cases

duplicate-two

{
  "args": [
    [
      1,
      3,
      4,
      2,
      2
    ]
  ]
}

Expected: 2

Wizard outline

Step 1: Initialize Solution.findDuplicate
Replace the empty starter with the first real state owned by Solution.findDuplicate. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Repeated Many case
Complete the readable core algorithm for one representative Interview case. Interpret each value as a next index and use Floyd's cycle algorithm to locate the repeated entry.
Step 3: Harden the Duplicate Two boundary
Repair the reviewed boundary and pass the complete submission contract. The n+1 indices map into values 1 through n, so following values must enter a cycle. The only merged destination on the path corresponds to the duplicate value. Floyd's second phase meets at that cycle entrance, therefore it returns the duplicate.

Footguns and prerequisites

Index zero is the traversal start; the duplicate value is the cycle entrance, not necessarily the first repeated element encountered during a scan.
arrays strings two pointers sliding window

Reviewed references

LeetCode 287 — Find the Duplicate Number

Practice prerequisites

Trace Fast and Slow Pointers(opens in a new tab)
Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing find duplicate number as a complete Interview Problem.

Recommended approach and implementation

Treat nums[index] as a next pointer. Find a meeting point with slow and fast pointers, then reset one pointer to index zero and advance both one step to the cycle entrance.

Why it works: The n+1 indices map into values 1 through n, so following values must enter a cycle. The only merged destination on the path corresponds to the duplicate value. Floyd's second phase meets at that cycle entrance, therefore it returns the duplicate.

class Solution:
    def findDuplicate(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        finder = 0
        while finder != slow:
            finder = nums[finder]
            slow = nums[slow]
        return finder