Find the Duplicate Number — InterviewPrepKit

Solving tips

The read-only + O(1)-space constraints are the whole problem; note that every value is a valid index, so treat i -> nums[i] as an implicit linked list.
A duplicate value means two indices point to the same node, creating a cycle whose entry IS the duplicate; use Floyd's tortoise-and-hare in O(n) time, O(1) space.
Phase 1 finds a meeting point inside the cycle; phase 2 (restart slow at index 0, advance both at speed 1) finds the entry, and both phase-1 pointers must start at index 0.
Don't return the phase-1 meeting point (it's not the entry); a binary-search-on-value-range alternative (count of x <= mid) is O(n log n), O(1) if you forget the graph view.

Problem

You are given an array nums of n + 1 integers, each in the range [1, n]. By pigeonhole, at least one value must appear more than once — and here exactly one value is repeated (possibly more than twice). Return that repeated value.

The twist: you must not modify the array, and you must use only O(1) extra space. (Sorting in place, or marking visited slots by negating entries, are both off the table.)

Examples

Input: nums = [1, 3, 4, 2, 2] → Output: 2 n = 4; the value 2 appears twice.
Input: nums = [3, 1, 3, 4, 2] → Output: 3 3 is the repeated value.
Input: nums = [3, 3, 3, 3, 3] → Output: 3 The duplicate may appear many times — still one answer.

Constraints

1 <= n <= 10^5, nums.length == n + 1
1 <= nums[i] <= n
Exactly one value is repeated (one or more extra times).
The array is read-only; only constant extra space allowed.

Think about it first

Hint 1

Without the read-only / O(1)-space rules this is trivial (sort, or a hash set). The rules are the problem. What structure do the values impose? Every entry is a valid index into the array.

Hint 2

Try counting instead of marking: for a candidate m, how many entries are ≤ m? If the count exceeds m, the duplicate lies in [1, m]. That's a binary search over values, not positions.

Hint 3

Treat i -> nums[i] as a linked list: start at index 0 and repeatedly jump to the index given by the current value. A duplicate value means two indices point at the same node — the walk enters a cycle whose entry point is the duplicate. Floyd's cycle detection finds it in O(n) time, O(1) space.

TL;DR

Floyd’s cycle detection on the implicit i -> nums[i] linked list — O(n) time, O(1) space, array untouched.

Approach 1 — Brute force: check every pair

Compare every pair of positions and return the value that appears at two of them.

from typing import List


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    return nums[i]
        return -1  # unreachable: a duplicate is guaranteed

Complexity: O(n^2) time, O(1) space.

It respects the read-only and space rules — but at n = 10^5 that’s ~5·10^9 comparisons, far past any time limit.

Approach 2 — Hash set (drops the space rule)

The insight: the first value you see twice is the answer; a set detects “seen before” in O(1). Worth writing in an interview as the baseline before honoring the O(1)-space constraint.

from typing import List


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

Walkthrough on [1, 3, 4, 2, 2]: seen grows {1}, {1,3}, {1,3,4}, {1,3,4,2}; the final 2 is already present → return 2.

Complexity: O(n) time, O(n) space — fast, but violates the constant-space requirement.

Approach 3 — Binary search on the value range

The insight: binary search doesn’t need a sorted array — it needs a monotone predicate. Let count(m) = how many entries are ≤ m. With values drawn from [1, n], if there were no duplicate then count(m) ≤ m for every m; a duplicate d inflates the count for every m ≥ d. So the predicate “count(m) > m” is false below d and true from d upward — binary search over values [1, n] for its flip point. (Binary search: the classical halving algorithm that finds the boundary of a monotone condition in logarithmically many probes.)

from typing import List


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        lo, hi = 1, len(nums) - 1  # search over VALUES 1..n
        while lo < hi:
            mid = (lo + hi) // 2
            count = sum(1 for x in nums if x <= mid)
            if count > mid:
                hi = mid       # duplicate is in [lo, mid]
            else:
                lo = mid + 1   # duplicate is in [mid+1, hi]
        return lo

Walkthrough on [1, 3, 4, 2, 2] (values 1..4): mid = 2, entries ≤ 2 are {1, 2, 2} → count 3 > 2, so hi = 2. Then mid = 1, entries ≤ 1 are {1} → count 1 ≤ 1, so lo = 2. lo == hi == 2 → return 2.

Complexity: O(n log n) time (a full scan per probe), O(1) space, read-only. Meets every rule — one log factor short of optimal.

Approach 4 — Floyd’s cycle detection (the linked-list view)

The insight: because every value is a valid index, i -> nums[i] defines a walk. Starting at index 0 (which nothing points to, since values are ≥ 1), the walk must eventually repeat an index — and a repeat can only happen because two different indices hold the same value, both jumping to the same place. So the walk is a ρ-shape: a tail, then a cycle, and the cycle’s entry node is the duplicate value. Floyd’s cycle-detection algorithm (tortoise and hare) finds the meeting point with two speeds, then finds the cycle entry by restarting one pointer at the start and advancing both at speed 1 — a classical theorem says they meet exactly at the entry.

from typing import List


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Phase 1: find a meeting point inside the cycle
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        # Phase 2: the cycle entry (= the duplicate) is equidistant
        # from the start and from the meeting point
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow

Walkthrough on [1, 3, 4, 2, 2] — the walk from 0 goes 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> ... (tail 0,1,3, cycle 2 <-> 4, entry 2):

phase 1 step	slow	fast
1	1	3
2	3	4
3	2	4
4	4	4 — met

Phase 2 from slow = 0, fast = 4: step 1 → slow 1, fast 2; step 2 → slow 3, fast 4; step 3 → slow 2, fast 2 — met at 2, the duplicate.

Complexity: O(n) time, O(1) space, array never written. This is the intended solution.

Common pitfalls

Starting Floyd’s pointers at nums[0] in one phase and 0 in the other inconsistently — both phase-1 pointers must start at the same node (index 0 works because no value is 0, so 0 is guaranteed to be outside the cycle).
Returning the phase-1 meeting point — it’s some node inside the cycle, not necessarily the entry; phase 2 is not optional.
In the binary search, searching over array indices instead of the value range [1, n] — the array isn’t sorted; only the counting predicate is monotone.
“Fixing” the space constraint by sorting a copy — sorted(nums) is O(n) extra space, which the follow-up forbids (and sorting in place modifies the input).

Pattern takeaway

When an array’s values are legal indices into itself, the array is a functional graph, and pointer techniques transfer wholesale: a duplicate value is two edges into one node, i.e. a cycle, and Floyd’s two-speed walk finds its entry in O(1) space. More broadly, constraints like “read-only + constant space” are hints to look for structure you can traverse rather than data you can store.