You are given an array nums of n + 1 integers where each integer is in the range [1, n] inclusive. Every integer appears exactly once except for one which appears two or more times. Return the integer that appears more than once.
Follow-up: solve without modifying the array and using O(1) extra space.
1. Sorting O(n log n) time · O(1) space — modifies array
Intuition
Sort the array so duplicates become adjacent, then scan for the first pair where nums[i] == nums[i+1].
Sort → O(n log n). One linear scan after.
Downside: modifies the input array.
Executing Code
deffindDuplicate(self, nums):
nums.sort()
for i inrange(len(nums) - 1):
if nums[i] == nums[i + 1]:
return nums[i]
return -1
Time: O(n log n) | Space: O(1) or O(n) depending on sort
2. Hash Set O(n) time · O(n) space
Intuition
Track seen values in a hash set. The first time we find a value already in the set, that's the duplicate. Simple and fast, but uses extra memory.
One pass, O(1) per lookup. Stop as soon as duplicate found.
Downside: O(n) extra space.
Executing Code
deffindDuplicate(self, nums):
seen = set()
for num in nums:
if num in seen: return num
seen.add(num)
return -1
Time: O(n) | Space: O(n)
3. Negative Marking O(n) time · O(1) space — modifies array
Intuition
Since values are in [1, n], each value maps to an index abs(num) - 1. Use the sign of nums[idx]as a visited flag — negate it when first visited. If it's already negative when we arrive, we've seen this value before.
O(1) extra space, but mutates the input. Restore by taking abs at the end if needed.
Downside: modifies the input array.
Executing Code
deffindDuplicate(self, nums):
for num in nums:
idx = abs(num) - 1
if nums[idx] < 0: returnabs(num)
nums[idx] *= -1
return -1
Time: O(n) | Space: O(1) extra (modifies input)
4. Binary Search on Value Range O(n log n) time · O(1) space
Intuition
Binary search on the value range[1..n], not on the array index. For midpoint mid, count elements ≤ mid in the array. By the Pigeonhole Principle: if count > mid, the duplicate is in [1..mid]; otherwise it's in [mid+1..n].
Each binary search iteration does an O(n) count pass → O(n log n) total.
Does not modify the array. O(1) space.
Executing Code
deffindDuplicate(self, nums):
n = len(nums); low, high = 1, n - 1
while low < high:
mid = low + (high - low) // 2
cnt = sum(1 for x in nums if x <= mid)
if cnt <= mid: low = mid + 1
else: high = mid
return low
Time: O(n log n) | Space: O(1)
5. Bit Manipulation O(32·n) time · O(1) space
Intuition
For each bit position b: count how many numbers in the array have bit b set (x), vs how many numbers in [1..n-1] should have it (y). If x > y, the duplicate contributes that extra bit. OR it into the result.
32 passes over n elements → O(32n). Reconstructs the duplicate bit-by-bit.
Does not modify the array. O(1) space.
Caveat: only correct when exactly one value is duplicated (even/odd cancellation).
Executing Code
deffindDuplicate(self, nums):
n = len(nums); res = 0
for b inrange(32):
x = y = 0; mask = 1 << b
for num in nums: if num & mask: x += 1
for num inrange(1, n): if num & mask: y += 1
if x > y: res |= mask
return res
Time: O(32·n) | Space: O(1)
6. Floyd's Cycle Detection O(n) time · O(1) space — optimal ★
Intuition
Treat the array as an implicit linked list: index i points to node nums[i]. Because one value is duplicated, two different indices point to the same next index — creating a cycle. The cycle's entry point is exactly the duplicate.
Floyd's algorithm finds the entry in two phases without extra space and without modifying the array.
Phase 1 — Detect: slow moves 1 step (slow = nums[slow]), fast moves 2 steps (fast = nums[nums[fast]]). They meet somewhere inside the cycle.
Phase 2 — Locate: reset slow2 = 0. Advance both slow and slow2 one step each. Where they meet is the cycle entry = duplicate.
The visualization breaks every move into its own step and highlights the arc being traversed.
STEP—
Press ▶ or step forward to begin.
✓
—
Space Play/Pause ·←→ Step ·R Reset ·F Fullscreen
Executing Code
deffindDuplicate(self, nums):
slow, fast = 0, 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast: break
slow2 = 0
while True:
slow = nums[slow]
slow2 = nums[slow2]
if slow == slow2: return slow
Time: O(n) | Space: O(1)
Common Pitfalls
Modifying the array when not allowed: sorting and negative marking both mutate the input. The follow-up asks for a non-mutating O(1) solution — use Floyd's or binary search.
Off-by-one in index mapping: values are [1..n] but indices are [0..n-1]. Always subtract 1: seen[num - 1], not seen[num].
Floyd's — first meet ≠ answer: the meeting point of slow and fast in Phase 1 is inside the cycle, not the entry. You must run Phase 2 (slow2 from index 0) to find the actual cycle entry = duplicate.
Binary search direction: if count ≤ mid, the duplicate is in the upper half [mid+1..high]. Reversing gives the wrong answer.
Bitmask — only for single duplicate: if a value appears 3 times, bit counts may cancel. The problem guarantees exactly one duplicate, so this is fine here.
Discussion
…