287. Find the Duplicate Number

Problem Statement

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 uses only constant extra space.

Pattern: Pattern 1-n range array Pattern Fast and Slow Pointer

---

todoleetcode

Solution

Notes

• This can also be solved via the self-freq array method . Negative mark an array, then unmark it
• Fast and slow pointer to find cycle, then find the start of the cycle

public int findDuplicate(int[] nums) {
	// Find the intersection point of the two runners.
	int tortoise = nums[0];
	int hare = nums[0];
	
	do {
		tortoise = nums[tortoise];
		hare = nums[nums[hare]];
	} while (tortoise != hare);
 
	// Find the "entrance" to the cycle.
	tortoise = nums[0];
	
	while (tortoise != hare) {
		tortoise = nums[tortoise];
		hare = nums[hare];
	}
	return hare;
}