Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints

• Read-only array (nums cannot be modified)
• Constant extra space (O(1) space)
• Runtime less than O(n²)

---

✅ Optimal Approach: Floyd’s Tortoise and Hare (Cycle Detection)

Think of the array as a linked list:

• Treat each element nums[i] as a pointer to the next index.
• Because there is a duplicate, there must be a cycle.

🔁 Steps:

1. Phase 1 (Finding intersection):
   • slow = nums[0]
   • fast = nums[nums[0]]
   • Move slow by 1 step, fast by 2 steps until they meet.
2. Phase 2 (Finding the entrance to the cycle = duplicate number):
   • Move one pointer back to start (slow = nums[0]).
   • Move both slow and fast one step at a time.
   • The point where they meet is the duplicate.

Code :

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        slow = nums[slow];
        fast = nums[nums[fast]];
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        slow = nums[0];
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

/*
TC : O(n)
SC : O(1)
*/

Dry-Run:

✅ Step-by-Step Dry Run

📌 Initialization:

cppCopyEditint slow = nums[0];  // slow = 1
int fast = nums[0];  // fast = 1

---

🔁 Phase 1: Detect intersection inside the cycle

Iteration 1:

cppCopyEditslow = nums[slow];        // slow = nums[1] = 3
fast = nums[nums[fast]];  // fast = nums[nums[1]] = nums[3] = 2

Now:

• slow = 3
• fast = 2

---

Iteration 2:

cppCopyEditslow = nums[slow];        // slow = nums[3] = 2
fast = nums[nums[fast]];  // fast = nums[nums[2]] = nums[4] = 2

Now:

• slow = 2
• fast = 2

🎯 Intersection found: both pointers at index 2.

---

🔁 Phase 2: Find entrance to cycle (duplicate number)

cppCopyEditslow = nums[0];  // slow = 1 (reset to start)
fast = 2         // stays where it is

---

Iteration 1:

cppCopyEditslow = nums[slow];  // slow = nums[1] = 3
fast = nums[fast];  // fast = nums[2] = 4

• slow = 3
• fast = 4

---

Iteration 2:

cppCopyEditslow = nums[slow];  // slow = nums[3] = 2
fast = nums[fast];  // fast = nums[4] = 2

• slow = 2
• fast = 2

🎯 Both meet at index 2, which is the duplicate number.

---

✅ Final Answer:

cppCopyEditreturn slow;  // 2

Simulating a Linked List Using the Array

Given:

cppCopyEditnums = [1, 3, 4, 2, 2]

• Indices: 0 1 2 3 4
• Values: 1 3 4 2 2

Think of each element as a pointer to another index — that is, from index i, go to nums[i].

Just like in a linked list where a node points to the next node, here each index points to the index stored in nums[i].

---

🧭 Let’s simulate:

We’ll start at index 0.

textCopyEditStart at index 0
nums[0] = 1 → go to index 1
nums[1] = 3 → go to index 3
nums[3] = 2 → go to index 2
nums[2] = 4 → go to index 4
nums[4] = 2 → go to index 2 (again!) 🚨 cycle starts here

---

🔁 Walkthrough in Link Format

markdownCopyEdit0 → 1 → 3 → 2 → 4
            ↑    |
            └────┘

Here:

• nums[0] = 1, so index 0 points to index 1
• nums[1] = 3, so index 1 points to index 3
• nums[3] = 2, so index 3 points to index 2
• nums[2] = 4, so index 2 points to index 4
• nums[4] = 2, so index 4 points back to index 2 → forms a cycle