DSA Find the Duplicate Number

The problem

The list holds n plus 1 values. Every value sits between 1 and n. Exactly one value repeats, and it may repeat more than twice.

The answer is the repeated value. The list must not be modified. The method in this article stores only two pointers.

cases = [
    ([1, 3, 4, 2, 2], 2),
    ([3, 1, 3, 4, 2], 3),
    ([2, 2, 2, 2], 2),
]
for nums, expected in cases:
    print("nums", nums, "-> duplicate:", expected)

The third row repeats its value at every position. The method must handle that row too. A value repeated many times is still the one repeated value.

Intuition: remember every value seen

The first idea stores each value as it is met. A value that is already stored is the duplicate. The idea is simple and correct.

nums = [1, 3, 4, 2, 2]
stored = []
for value in nums:
    if value in stored:
        print("value", value, "was already stored; it is the duplicate")
        break
    stored.append(value)
    print("value", value, "stored; stored now:", stored)

The cost is memory. The stored list grows to nearly the size of the input. The rest of the article removes that cost.

Brute force: compare every pair

The brute force compares each pair of positions once. Equal values at two positions expose the duplicate. A counter records the comparisons.

This version stores nothing. It pays in comparisons instead. A late duplicate pair costs nearly every comparison in the list.

def brute(nums):
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
            if nums[i] == nums[j]:
                return nums[i], checks
    return None, checks

for nums in [[1, 3, 4, 2, 2], [3, 1, 3, 4, 2], [2, 2, 2, 2]]:
    dup, checks = brute(nums)
    print(nums, "-> duplicate:", dup, "comparisons:", checks)

The all-same row answers after one comparison. The first row needs all ten. Which row is cheap depends on where the twin positions sit, and the search cannot know in advance.

The optimal solution: read the list as a chain of pointers

The state is two pointers walking one chain. Each index points at the value it holds, the chain must eventually loop because every step lands on another index, and the loop's entry point, its door, is the value that two indices point at.

That door is the duplicate. Two indices hold it as their target, so it appears twice as a pointed-to value. Floyd's algorithm finds the door in two phases, meeting inside the loop first and then walking two pointers at the same speed to the door.

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    rounds = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
        rounds += 1
    finder = 0
    steps = 0
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]
        steps += 1
    return finder, rounds, steps

cases = [
    ([1, 3, 4, 2, 2], 2),
    ([3, 1, 3, 4, 2], 3),
    ([2, 2, 2, 2], 2),
]
for nums, expected in cases:
    dup, rounds, steps = find_duplicate(nums)
    print(nums, "-> duplicate:", dup, "match:", dup == expected, "phase one rounds:", rounds, "phase two steps:", steps)

All three cases match. The list is never written to. Only the two pointers and two counters exist beside the input.

Walkthrough: the chain in [1, 3, 4, 2, 2]

The walk traces both phases on the first case. Index 3 and index 4 both point at 2. The chain from index 0 runs 1, 3, 2, 4, then back to 2.

nums = [1, 3, 4, 2, 2]
slow = nums[0]
fast = nums[nums[0]]
print("phase one starts: slow", slow, "fast", fast)
while slow != fast:
    slow = nums[slow]
    fast = nums[nums[fast]]
    print("slow moves to", slow, " fast moves to", fast)
print("they meet at", slow, "inside the loop")
finder = 0
while finder != slow:
    finder = nums[finder]
    slow = nums[slow]
    print("finder moves to", finder, " slow moves to", slow)
print("both arrive at", finder, "the door and the duplicate")

The meeting point, 4, is inside the loop but is not the door. Phase two is not optional. Skipping it and reporting the meeting point is the classic wrong answer for this method.

Complexity

Each phase walks the chain at most a few times over, so the time is O(n). Only two pointers are stored, so the extra space is O(1).

The brute force compares up to n times n minus 1, divided by 2, pairs. The counts below run both methods on lists whose duplicate sits at the very end, the brute force's worst spot.

def brute_checks(nums):
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
            if nums[i] == nums[j]:
                return checks
    return checks

def floyd_steps(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    steps = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
        steps += 1
    finder = 0
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]
        steps += 1
    return steps

for n in [4, 9, 19]:
    nums = list(range(1, n + 1)) + [n]
    print("values", len(nums), "- brute comparisons:", brute_checks(nums), " floyd steps:", floyd_steps(nums))

At 20 values the pair count is 190 against 37 pointer steps. The pointer method also leaves the input untouched, which the pair scan does too but the stored-values scan's memory does not allow at scale.

Edge cases and pitfalls

The smallest list is two copies of 1. A value repeated at every position still forms a loop with a door. A duplicate whose copies sit at the end costs phase two only a few steps.

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    rounds = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
        rounds += 1
    finder = 0
    steps = 0
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]
        steps += 1
    return finder, rounds, steps

for nums in [[1, 1], [2, 2, 2, 2], [3, 3, 1, 2], [1, 2, 3, 3]]:
    dup, rounds, steps = find_duplicate(nums)
    print(nums, "-> duplicate:", dup)

One pitfall sits in phase one's first step. The fast pointer must start two steps ahead, or the two pointers begin equal and the meeting loop never runs. The starting positions in the code above keep them apart.