Find the Duplicate Number in Python Using Floyd's Cycle Detection

Detects the duplicate integer in an array of n+1 numbers (values 1 to n) in O(n) time and O(1) space using Floyd's cycle detection algorithm applied to a linked-list model.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 14 views 0 copies

floyd-cycle duplicate-number two-pointers algorithms linked-list

Python code

31 lines
Python 3.9+
Run it 
def find_duplicate(nums):
    slow = nums[0]
    fast = nums[0]
    
    # Phase 1: Find intersection point of the cycle
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    # Phase 2: Find the start of the cycle (the duplicate)
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow

if __name__ == "__main__":
    # Example array: length n+1, values in range [1, n], one duplicate guaranteed
    test_cases = [
        [1, 3, 4, 2, 2],
        [3, 1, 3, 4, 2],
        [1, 1],
        [2, 2, 2, 2, 2]
    ]
    
    for arr in test_cases:
        duplicate = find_duplicate(arr)
        print(f"Array: {arr} -> Duplicate: {duplicate}")

Output

stdout 
Array: [1, 3, 4, 2, 2] -> Duplicate: 2
Array: [3, 1, 3, 4, 2] -> Duplicate: 3
Array: [1, 1] -> Duplicate: 1
Array: [2, 2, 2, 2, 2] -> Duplicate: 2

How it works

The array is treated as a linked list where each value points to the next index. Because there's a duplicate, this implicit list contains a cycle. Phase 1 finds a meeting point inside the cycle using a fast pointer that moves two steps and a slow pointer that moves one. Phase 2 resets one pointer to the start and moves both at the same speed; the point where they meet is the cycle's entry, which corresponds to the duplicate value. This approach meets the requirement of O(1) extra space and avoids modifying the array.

Common mistakes

  • Forgetting the problem guarantee that values are in [1, n] and using index 0 incorrectly.
  • Treating the array as a value array instead of an index-pointer structure.
  • Using extra sets or sorting, which violates the O(1) space or O(n) time constraints.
  • Not handling the case where the duplicate appears more than twice (e.g., [2, 2, 2, 2, 2]).

Variations

  1. Use a set to track seen numbers, but that uses O(n) space and is simpler.
  2. Sort the array and scan adjacent pairs, but that modifies the input and costs O(n log n).

Real-world use cases

  • Finding a repeated record ID in a fixed-size range without extra storage.
  • Detecting a duplicate in a batch of sensor readings constrained to a known value range.
  • Identifying a repeated transaction ID in a log file where memory is limited.

Sponsored

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Algorithms & data structures

Keep learning

Related tutorials and quizzes for this topic.

Tutorials

Quizzes