Find Duplicate Number using Floyd’s Cycle Detection - problem and solution in Java and Python

This one is a very popular FAANG interview problem 👇

Let’s go step-by-step and make it super clear.

---

🧩 Problem: Find the Duplicate Number

You are given an array of n + 1 integers where each integer is between 1 and n (inclusive). There is only one repeated number, but it could appear multiple times.

Your job: 👉 Find that duplicate number without modifying the array and using constant extra space (O(1)).

---

🧠 Example

Input: [1, 3, 4, 2, 2]
Output: 2

Another example:

Input: [3, 1, 3, 4, 2]
Output: 3

---

⚙️ Naive / Brute Force Approaches

1. Sorting

   • Sort the array and check adjacent elements.
   • Time: O(n log n)
   • Space: O(1) if done in place ❌ But it modifies the array, which the problem forbids.

2. HashSet

   • Keep a set of visited numbers.
   • If you see a number again → that’s the duplicate.
   • Time: O(n)
   • Space: O(n) ❌ Not constant space.

---

🚀 Optimized Approach — Floyd’s Cycle Detection (Tortoise & Hare)

This is the most elegant and FAANG-standard solution.

---

🧠 Intuition

• Think of the array as a linked list where each index points to the next index based on its value. For example:

  nums = [1, 3, 4, 2, 2]
  index: 0  1  2  3  4
  value: 1  3  4  2  2
  

  So you can think of the “next” pointer as:

  0 → 1 → 3 → 2 → 4 → 2 (cycle starts here)
  

• Because one number repeats, it creates a cycle in this linked list.

• We can use Floyd’s Cycle Detection Algorithm (Tortoise and Hare) to find the start of that cycle → the duplicate.

---

🧭 Algorithm Steps

1. Phase 1 – Detect intersection point

   • Use two pointers:

     • slow = nums[slow]
     • fast = nums[nums[fast]]

   • Move until they meet.

2. Phase 2 – Find entrance to the cycle

   • Reset one pointer (say slow) to the start.

   • Move both one step at a time:

     • slow = nums[slow]
     • fast = nums[fast]

   • The point where they meet again is the duplicate number.

---

💻 Java Implementation

public class FindDuplicateNumber {
    public static int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // Phase 1: Find the intersection point
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: Find entrance to the cycle
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 2, 2};
        System.out.println(findDuplicate(nums)); // Output: 2
    }
}

---

💻 Python Implementation

def findDuplicate(nums):
    # Phase 1: Find intersection
    slow = nums[0]
    fast = nums[0]
    
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    # Phase 2: Find entrance
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow

print(findDuplicate([1, 3, 4, 2, 2]))  # Output: 2

---

⚡ Time & Space Complexity

Complexity	Description
Time	O(n)
Space	O(1) (constant space)
Does Not Modify Array	✅ Yes

---

🧒 Explaining to a Kid

Imagine a maze where every room has a door number telling you which room to go next. But one door takes you back to a room you already visited — so you keep looping forever 🌀

You send:

• 🐢 Tortoise (slow — one door at a time)
• 🐇 Hare (fast — two doors at a time)

They eventually meet inside the loop. Then, you move both slowly again — and when they meet again, that’s the room number with the duplicate door!

---

🔁 Alternate Approach (Hashing)

If constant space is not a concern:

def findDuplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return n
        seen.add(n)

Simple — but uses O(n) space.

---