Find Duplicate
While placing numbers at their correct indices, if the destination already has the correct value, the current number must be a duplicate. No extra space needed.
How It Works
Finding a duplicate with cyclic sort uses the placement process as a detector. Try to swap each element to its home index; if the value already sitting at that home equals the value you are trying to place, the swap would be pointless — you are holding a second copy, and that value is the duplicate.
The technique runs in O(n) time and O(1) space but rearranges the array. When the input must stay read-only — the constraint in Find the Duplicate Number — the standard alternative treats values as pointers and applies Floyd's cycle detection, at the same asymptotic cost. Compared with sorting first (O(n log n)) or a hash set (O(n) extra memory), cyclic placement gets both optimal time and constant space when mutation is allowed.
Step-by-Step Visualization
Code
static int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length) {
if (nums[i] != i + 1) {
int correct = nums[i] - 1;
if (nums[i] == nums[correct]) return nums[i]; // Duplicate!
int tmp = nums[i]; nums[i] = nums[correct]; nums[correct] = tmp;
} else i++;
}
return -1;
}Tips & Gotchas
Practice Problems
- 1Find the Duplicate Number
- 2Find All Duplicates in an Array
- 3Set Mismatch
About the Cyclic Sort Pattern
When an array contains numbers in the range [1, n] (or [0, n]), you can place each number at its 'correct' index (number i goes to index i−1). After sorting, any index without its correct number reveals the missing or duplicate value.
When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.
Common Array Interview Problems
- Two Sum
- Best Time to Buy & Sell Stock
- Maximum Subarray
- Merge Intervals
- Product of Array Except Self
- Container With Most Water
Frequently Asked Questions
How does the swap loop actually notice the duplicate?
Before swapping element v toward index v−1, compare it with the occupant of that index. If nums[v−1] already equals v, a second copy of v exists in your hand; depending on the problem you record it and move on, or return it immediately.
What if the array cannot be modified?
Use Floyd's fast and slow pointers over the implicit linked list where index i points to nums[i]; the duplicate creates a cycle whose entrance is the repeated value. That preserves O(n) time and O(1) space without any writes, which is why interviewers often add the read-only constraint.
Can this find every duplicate, not just one?
Yes — after cyclic placement finishes, any index whose occupant does not match its home value holds a duplicate, and one collection pass gathers them all. The index-negation-marking variant achieves the same result while nominally keeping values in place.