Find The Duplicate Number

This looks like an array problem, but the constraints hide a linked list in disguise: since every value is in [1, n] and the array has n + 1 slots, you can treat nums[i] as “a pointer from index i to index nums[i]”. Because two different indices are forced to point at the duplicate value, that implicit pointer structure must contain a cycle — and finding a cycle’s entrance is exactly Floyd’s algorithm from the Linked List Cycle problem.

Hash Set

Time O(n)Space O(n)

Walk the array once, remembering every value seen. The first value seen twice is the duplicate.

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)
        return -1

Correct and simple, but the problem explicitly asks for constant extra space — a hash set of up to n elements does not qualify.

Binary Search on the Answer

Time O(n log n)Space O(1)

Binary search over the value range [1, n] rather than over the array itself. For a candidate midpoint mid, count how many numbers in the array are <= mid. By the pigeonhole principle, if that count exceeds mid, the duplicate must be in [1, mid] (too many values are crammed into too few slots); otherwise it’s in [mid+1, n].

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        lo, hi = 1, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            count = sum(1 for x in nums if x <= mid)
            if count > mid:
                hi = mid
            else:
                lo = mid + 1
        return lo

This satisfies the constant-space requirement, but each of the O(log n) binary search steps rescans the whole array to count, costing O(n log n) time overall — slower than necessary.

Floyd's Cycle Detection

OptimalTime O(n)Space O(1)

Treat nums as a function: from index i, “hop” to index nums[i]. Since values only range over [1, n] but there are n + 1 indices, at least two indices must hop to the same place — the duplicate value is the node where two different paths merge, i.e. the entrance to a cycle. Find it with the exact same two-pointer technique used to detect a cycle in a linked list: a fast/slow phase to find any point on the cycle, then a second phase (resetting one pointer to the start and advancing both one step at a time) to find where the cycle begins.

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        # Phase 1: find a meeting point somewhere on the cycle
        slow = fast = nums[0]
        slow = nums[slow]
        fast = nums[nums[fast]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]

        # Phase 2: find the entrance to the cycle (the duplicate)
        slow2 = nums[0]
        while slow2 != slow:
            slow2 = nums[slow2]
            slow = nums[slow]
        return slow

Tracing nums = [1,3,4,2,2] — indices 3 and 4 both “point to” index 2 (nums[3] = nums[4] = 2), which is exactly why 2 is the duplicate:

slowfast

phase = Phase 1

1 / 6

comparingresultcurrent

Both pointers take their first hop from the implicit start to index 1 (nums[0] = 1).

Why it’s correct: viewing nums as pointers i -> nums[i] forms an implicit linked structure that must contain a cycle, because two indices (the duplicate’s two occurrences) both point to the same next index. Floyd’s algorithm finds that cycle’s entrance in the same way it finds where a linked list starts repeating — and the entrance is precisely the duplicated value, since it’s the only node with two incoming “pointers.” Complexity: phase 1 and phase 2 each take at most O(n) hops with two pointer variables → O(n) time, O(1) space — this is optimal and satisfies both the space constraint and the linear-time follow-up, without modifying the array.