-
Notifications
You must be signed in to change notification settings - Fork 0
072 — Find the Duplicate Number
LeetCode 287 · Medium. Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is exactly one repeated number (it may repeat more than once). Find that repeated number, without modifying the array, using only O(1) extra space.
This one hides its true shape behind an array. Nothing here looks like a linked list — it's just [Int]. But look closer at what a value in this array actually means: nums[i] is always a number between 1 and n, which is always a valid index back into the same array. So instead of thinking of nums as data, think of it as a set of arrows: index i points to index nums[i]. Follow those arrows starting from index 0, and you're walking an implicit linked list built entirely out of array indices. Because there are n+1 values crammed into a range of only n possible values, the pigeonhole principle guarantees at least one duplicate — and that duplicate value means two different indices point to the same next stop, which is exactly what creates a cycle in this implicit list.
"Array of n+1 integers in range [1, n]" plus "find the duplicate" plus "O(1) space, don't modify the array" is the specific combination that signals this trick. The array-shape disguise is deliberate — the real cue is the constraint that values map back into valid indices of the same array, which is what makes "treat nums[i] as a pointer to index nums[i]" possible at all. Once you see that, it's a Fast and Slow Pointers cycle-detection problem wearing an array costume.
Track every value seen in a hash set; the first repeat is the answer.
func findDuplicateBruteForce(_ nums: [Int]) -> Int {
var seen = Set<Int>()
for num in nums {
if seen.contains(num) {
return num
}
seen.insert(num)
}
return -1 // unreachable given the problem's guarantee of exactly one duplicate
}
// smoke test
print(findDuplicateBruteForce([1, 3, 4, 2, 2])) // 2
print(findDuplicateBruteForce([3, 1, 3, 4, 2])) // 3Big-O: O(n) time — one pass, O(1) average work per element. O(n) extra space for the hash set — this is the constraint the optimal solution is specifically asked to avoid.
Treat nums[i] as "the index to go to next," which turns the array into an implicit linked list guaranteed to contain a cycle — then find that cycle's entrance with Floyd's algorithm, exactly as in Linked List Cycle II.
func findDuplicate(_ nums: [Int]) -> Int {
var slow = nums[0]
var fast = nums[0]
// Phase 1: race until slow and fast meet somewhere inside the cycle.
repeat {
slow = nums[slow]
fast = nums[nums[fast]]
} while slow != fast
// Phase 2: reset one pointer to the start, advance both by 1 —
// they're guaranteed to meet exactly at the cycle's entrance,
// which is the duplicate value.
slow = nums[0]
while slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
// smoke test
print(findDuplicate([1, 3, 4, 2, 2])) // 2
print(findDuplicate([3, 1, 3, 4, 2])) // 3Big-O: O(n) time — both phases are bounded by a constant multiple of n steps (standard Floyd's cycle-detection bound). O(1) extra space — just two integer pointers, and the input array is never modified.
The hash set brute force works by remembering every value it's seen — O(n) space spent purely on memory. The optimal solution instead notices that the constraints (n+1 values, each in [1, n]) secretly build a linked list for free: index 0 points to index nums[0], which points to index nums[nums[0]], and so on, with every "node" being an array slot and every "pointer" being the value stored there. Because two or more indices are forced to point at the same value (the duplicate), that implicit list can't terminate cleanly at some "end" — it must loop, and the node where two different paths converge (the cycle's entrance) is precisely the duplicated value. That reframing is what lets Floyd's O(1)-space cycle detection — built for actual linked lists — apply directly to a plain array.
-
Arrays & Strings — the actual data structure here; there's no real linked list in this problem, only an
[Int]array being treated as one. -
Fast and Slow Pointers — the array is walked as an implicit linked list where
nums[i]plays the role of "the pointer stored at indexi," and Floyd's cycle detection finds the duplicate as the cycle's entrance, exactly as in Linked List Cycle. - Linked List Cycle — the literal version of this same two-phase Floyd's algorithm, applied here to array indices instead of real node references.
Find the Duplicate Number is an array wearing a linked-list costume — nums[i] is really "the next stop," and the forced duplicate is exactly what makes that implicit list loop.
For nums = [1, 3, 4, 2, 2], draw out the implicit linked list starting at index 0: index 0 points to nums[0] = 1, index 1 points to nums[1] = 3, and so on. Identify where the cycle begins in this drawing, and confirm it matches the value returned by findDuplicate. Then explain in one sentence why the problem's constraint "n+1 values in range [1, n]" is exactly what guarantees a cycle must exist.