02
Duplicate number (Cyclic Sort Sub-pattern)
A repeated value finds its home already taken. Catch it there: as a squatter after cyclic sort, as an already-negative mark, or as the start of a cycle when you may not touch the array.
Signals in the problem statement
- ›
"find all duplicates" in 1..n with O(1) space
- ›
"two repeating elements", reported in the order they repeat
- ›
"find the duplicate" without modifying the array
What makes it different
The rules decide the tool. If you may change the array, use cyclic sort: squatters are the duplicates (LC 442). If the order of repeats matters, use sign marking: it's one left-to-right pass, so you see each repeat at its second occurrence. If the array is read-only, use Floyd's cycle on i → nums[i], or binary search on the value with counting as the simpler O(N log N) fallback (LC 287).
Questions
ordered from “learn the idea” to “recognise it without help”- 1Find All Duplicates in an ArrayWalkthroughMediumBasic Anchor·LeetCode #442
- 2Find the Two Repeating ElementsWalkthroughMediumSlight Variation·GeeksforGeeks
- 3Find the Duplicate NumberWalkthroughMediumPattern Transfer·LeetCode #287
Template
mark-template.cpp
// Values 1..n: flip nums[x - 1] negative to remember "x was seen".
// One left-to-right pass, so each repeat is found at its second occurrence.
vector<int> repeatsInOrder(vector<int>& nums) {
vector<int> repeats;
for (int i = 0; i < (int)nums.size(); i++) {
int x = abs(nums[i]); // this slot may already be flipped
if (nums[x - 1] < 0) repeats.push_back(x); // seen before → repeat
else nums[x - 1] = -nums[x - 1]; // first time: mark it
}
for (int& v : nums) v = abs(v); // optional: undo the marks
return repeats;
}Remember this · Cyclic Sort
Trigger
Numbers in range 1..n or 0..n, find missing / duplicate / both, O(1) extra space.
Think
Can value v live at index v−1? Then put everyone home and look for squatters.
Key question
Where does value v belong, and when do I stop swapping?