Find the Duplicate Number

Description

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:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

Approach - Hare Tortoise

• slow fast pointer like the linked list if both meet then it is a loop but doesn’t necessarily mean that is the duplicate, the duplicate we will find by finding the entrance of the of the loop
• Time: O(n)
  • Each pointer moves at most O(n) steps across both phases.
• Space: O(1) extra
  • Only a handful of pointers and counters, no arrays or recursion.

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
 
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
 
        return slow;
    }
}

Since each element in nums is a value between $1$ and $n$, you can treat each element as a pointer to another index in the array (e.g., nums[i] points to index nums[i]).

Because there is a duplicate value, two different indices will point to the same index, which creates a cycle (just like in a linked list). Finding the duplicate number is simply finding the entry point of the cycle.

The 2-Phase Strategy:

1. Phase 1 (Find the Intersection Point):

   • Use two pointers: slow moves 1 step at a time (slow = nums[slow]), and fast moves 2 steps at a time (fast = nums[nums[fast]]).
   • They will eventually meet inside the cycle.

2. Phase 2 (Find the Start of the Cycle / Duplicate):

   • Keep fast (or slow) at the meeting point and reset the other pointer to the start (0).
   • Move both pointers 1 step at a time.
   • The index where they meet again is the duplicate number!

The trick to seeing the similarity is realizing that an array can act as a pointer lookup table.
In a linked list, every node explicitly stores a pointer to the next node:

• node = node.next
  In an array, values are in the range $1$ to $n$, which means every value nums[i] is a valid index in the same array! So you can use array values as pointers:
• index = nums[index]

---

Mapping Array to Linked List

Think of the index as a node’s address, and the value stored at that index as the next pointer.

Index (node)	Value (node.next)	Pointer View
0	1	Node 0 points to Node 1
1	3	Node 1 points to Node 3
2	4	Node 2 points to Node 4
3	2	Node 3 points to Node 2
4	2	Node 4 points to Node 2

If you traverse this starting at index 0:

• Start at Index 0 $\to$ value is 1 (go to index 1)
• Index 1 $\to$ value is 3 (go to index 3)
• Index 3 $\to$ value is 2 (go to index 2)
• Index 2 $\to$ value is 4 (go to index 4)
• Index 4 $\to$ value is 2 (go to index 2 $\to$ CYCLE!)

---

Why Does a Duplicate Create a Cycle?

A cycle in a linked list happens when two different nodes point to the same next node.
In this array, both index 3 and index 4 contain the value 2. That means both index 3 and index 4 point to index 2.

0 -> 1 -> 3 -> 2 -> 4
               ^    |
               |____|

• Multiple pointers entering the same node = A Cycle.
• The entry point of that cycle = The Duplicate Number.

Because two different indices hold the number 2, traversing the array via nums[i] forces you into a loop at index 2. Finding the start of the cycle finds the duplicate!

Using while instead of do while

Yes, absolutely! You can write Phase 1 using a normal while (true) loop instead of a do-while loop.

The only reason people often use do-while is because slow and fast both start at index 0 (i.e., slow == fast initially). If you use a standard while (slow != fast) at the start, the loop won’t even execute once!

To use a normal while loop, simply take the first step before entering the loop:

class Solution {
    public int findDuplicate(int[] nums) {
        // Take the FIRST step manually so slow != fast when entering the loop
        int slow = nums[0];
        int fast = nums[nums[0]];
        
        // Normal while loop works now!
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        // Phase 2: Find the entry point of the cycle
        slow = 0; // Reset slow to the start index
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
}

Key Differences to Notice:

1. Initial values: fast starts at nums[nums[0]] (2 steps ahead) instead of nums[0].
2. Phase 2 reset: slow resets to index 0 (the start address), not nums[0].
   This does the exact same thing as a linked list traversal with while loops!

Brute Force Approach (Nested Loops)

Intuition:
Pick the first element, check if it appears anywhere else in the array. If it does, that’s your duplicate. If not, move to the next element and repeat.

Algorithm:

1. Loop through each index i from 0 to n-1.
2. Loop through every index j from i + 1 to n.
3. If nums[i] == nums[j], return nums[i].

class Solution {
    public int findDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }
        return -1;
    }
}

• Time Complexity: $\mathcal{O}(n^2)$
• Space Complexity: $\mathcal{O}(1)$

---

Here is the cleanest, most standard way to write Floyd’s Cycle Detection. Using slow = 0 and fast = 0 up front allows you to use one do-while loop followed by one while loop, which maps perfectly to the textbook definition of the algorithm.

---

The 2-Step Mental Blueprint

• Step 1 (Find Intersection): Start both pointers at the head (0). Move slow 1 step and fast 2 steps repeatedly using a do-while loop until they collide inside the cycle.
• Step 2 (Find Cycle Entry): Reset slow back to the head (0) while leaving fast at the collision point. Move both 1 step at a time using a while loop until they meet again. That meeting point is the duplicate!

---

class Solution {
    public int findDuplicate(int[] nums) {
        // Start both at the head (index 0)
        int slow = 0;
        int fast = 0;
        
        // Phase 1: Move first, then check if they met
        do {
            slow = nums[slow];           // 1 step
            fast = nums[nums[fast]];     // 2 steps
        } while (slow != fast);
        
        // Phase 2: Reset slow to start, move both 1 step at a time
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];           // 1 step
            fast = nums[fast];           // 1 step
        }
        
        return slow; // Cycle entrance = Duplicate number
    }
}
 

---

Is do-while followed by while the best way to remember it?

Yes, absolutely. Here is why this structure is superior for memorization:

• Symmetry: Both pointers start at index 0. Phase 2 resets slow back to index 0. You don’t have to guess whether to use 0 or nums[0].
• No Manual First Step: If you used standard while loops for both, you’d have to manually advance slow and fast before Phase 1 to prevent while (slow != fast) from exiting immediately.
• Direct Alignment: The do-while loop enforces “move first, then compare”, which prevents the initial slow == fast == 0 trap effortlessly.