Find the Duplicate Number
Medium · Two Pointers · Array · Two Pointers · Binary Search · Bit Manipulation
Problem
nums holds n + 1 integers, each between 1 and n. With more values than possible numbers, something must repeat — and here exactly one value does, possibly more than twice, while every other value appears at most once. Return that value.
Two rules make it interesting: you may not modify nums (no sorting it, no marking it), and you may use only O(1) extra space (no set of values seen). Aim for better than O(n²) time.
The tests check both rules they can see: your answer, and that nums is exactly as it was after your call. That is why each test’s expected value is shown as [duplicate, nums].
Examples
Input: nums = [1,3,4,2,2] Output: 2
Five values from 1 to 4: 2 appears twice.
Input: nums = [3,3,3,3,3] Output: 3
The duplicate may fill the array; 1, 2 and 4 simply do not appear.
Constraints
- 1 <= n <= 10^5
- len(nums) == n + 1
- 1 <= nums[i] <= n
- exactly one value appears two or more times; every other value at most once
- do not modify nums; use O(1) extra space
Approaches
- Remember what you have seen — time O(n), space O(n)
Follow-up
Why must a duplicate exist at all? And can you find it in linear time with O(1) extra space, without modifying nums?
Related problems
Start free on Cariara · Coding problems · System design studio
