Two Pointers - Find the Duplicate Number

Given an array of n+1 integers where each integer is between 1 and n, find the duplicate number. Must not modify the array and use only O(1) extra space.

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

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

Treat array as a linked list with cycle (Floyd's algorithm). Index i points to nums[i]. The duplicate creates a cycle. Find the cycle start.

Use slow = nums[nums[slow]] and fast = nums[fast] (like linked list).
Find intersection point inside cycle.
Then use two slow pointers from start and intersection to find cycle entrance (= duplicate).

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; } }

Time Complexity: O(N)
Space Complexity: O(1)