Find The Duplicate Number

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 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.

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

Watching the two pointers hop through the implicit index graph shows why their first meeting point is only on the cycle, and how the phase-2 reset then walks both of them into the cycle entrance:

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.