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
def findDuplicate(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 is about 5·10^9 comparisons, far past any time limit.
Approach 2 — Hash set (drops the space rule)
The first value seen twice is the answer, and a set detects “seen before” in O(1). This is the baseline to state in an interview before addressing the O(1)-space constraint.
from typing import List
def findDuplicate(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
Binary search does not need a sorted array; it needs a monotone predicate. Let count(m) be the number of entries ≤ 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] finds that flip point.
from typing import List
def findDuplicate(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, but is one log factor short of optimal.
Approach 4 — Floyd’s cycle detection (the linked-list view)
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 forms a ρ-shape: a tail, then a cycle, and the cycle’s entry node is the duplicate value.
For [1, 3, 4, 2, 2] the walk looks like this (each node is an array index; the edge from index i goes to index nums[i]):
flowchart LR
A["index 0"] --> B["index 1"]
B --> C["index 3"]
C --> D["index 2 (duplicate)"]
D --> E["index 4"]
E --> D
Indices 2 and 4 form the cycle, and index 2 is where the tail joins it, so the duplicate value is 2.
Floyd’s cycle-detection algorithm (tortoise and hare) finds a 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 result guarantees they meet exactly at the entry.
from typing import List
def findDuplicate(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.