LeetCode 287 · Medium · Linked List

Find the Duplicate Number

nums holds n + 1 integers, each between 1 and n, so at least one value repeats; exactly one value does. Return it without modifying the array and with O(1) extra space.

O(n)time
O(1)space
Floydi → nums[i] is a linked list

2–11 integers · each from 1 to (count − 1) · exactly one value repeats (it may repeat more than twice)

nums value nums[i] above its index i

As a linked list node i → node nums[i] · row 1 = the path from 0 · row 2 = indices the path never reaches

public int findDuplicate(int[] nums) { int slow = 0; int fast = 0; while (true) { // phase 1: meet inside the cycle slow = nums[slow]; fast = nums[nums[fast]]; if (slow == fast) { break; } } int slow2 = 0; while (true) { // phase 2: walk to the entrance slow = nums[slow]; slow2 = nums[slow2]; if (slow == slow2) { return slow; } }}
slow
—
fast
—
slow2
—
phase-1 rounds
0

Why it works

  1. Brute force: sort a copy, or keep a set of seen values. O(n log n) time or O(n) space, and sorting in place modifies the array, which the problem forbids.
  2. Read the array as a linked list: index i points to index nums[i]. No value is 0, so nothing points back to node 0 and the walk from 0 must eventually repeat. The duplicate value is the one node with two incoming arrows: the entrance of the cycle.
  3. Floyd, phase 1: fast gains one node per round on slow, so once both are in the cycle they meet within one lap. Phase 2: if the tail has length T and the cycle length C, the meeting point is T steps (mod C) short of the entrance, so a pointer from 0 and one from the meeting point, both moving 1 step, arrive at the entrance together.
  4. O(n) time, O(1) space: each phase takes at most a few laps of at most n + 1 nodes, and the only state is three indices.
  5. Pitfall: return the entrance, not the meeting point. slow and fast can meet anywhere on the cycle; only phase 2 lands on the node with two parents. And start at index 0, which is never anyone's target, so it is guaranteed to be outside the cycle.
  6. Related: Linked List Cycle II (142) is the same two phases on a real list. Binary search on the value range (count how many values are ≤ mid) is an O(n log n), O(1)-space alternative.