Cycle sort on LeetCode is the pattern behind a group of array problems that look unrelated on the problem list and turn out to be the same eight lines of C++ with a different last paragraph. Six of them are below: 268, 448, 287, 645, 442, and 41. If you can write the skeleton from memory, you can solve all six, and the Hard one stops being a Hard.
All the code here compiles and runs against the sample cases plus the edge cases listed at the bottom. More problems: the LeetCode series.
The six problems at a glance
| # | Problem | Difficulty | What it asks for |
|---|---|---|---|
| 268 | Missing Number | Easy | The one value from 0…n that isn’t there |
| 448 | Find All Numbers Disappeared in an Array | Easy | Every value from 1…n that isn’t there |
| 287 | Find the Duplicate Number | Medium | The one value that repeats |
| 645 | Set Mismatch | Easy | The repeated value and the missing one |
| 442 | Find All Duplicates in an Array | Medium | Every value that appears twice |
| 41 | First Missing Positive | Hard | The smallest absent positive integer |
What cycle sort is
Cycle sort is not a general-purpose sort. It only works when every value already knows which index it belongs at. That happens when the values are a permutation of the index range, give or take a fixed offset: value v belongs at index v, or at index v - 1, and nothing else needs deciding.
Given that, the algorithm is three rules. Walk the array. If the value at the current index is already home, move on. If it isn’t, swap it to where it belongs, then look at whatever just arrived and repeat, until the current slot holds something that belongs there or something you’ve agreed to leave alone.
That’s the whole pattern:
int n = (int)nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] != i + 1) { // is the value at i already home?
int dest = nums[i] - 1; // where it belongs
if (nums[dest] == nums[i]) break; // that slot already holds this value
swap(nums[i], nums[dest]); // send it home, then look at what arrived
}
}
// second pass: every index holding the wrong value tells you somethingThe break is the line people leave out, and it is the difference between an accepted solution and an infinite loop. When two copies of the same value exist, the second one can never go home, because the first one is already sitting there. Without that check the two of them swap back and forth forever.
Everything below is that block with a different offset, a different reason to stop, and a different second pass. Here is the entire difference between the six problems:
| # | Value v belongs at | Stop swapping when | Second pass reports |
|---|---|---|---|
| 268 | index v | v == n (n has no slot) | the first i where nums[i] != i, else n |
| 448 | index v - 1 | the destination already holds v | i + 1 for every mismatched index |
| 287 | index v - 1 | the destination already holds v — and that’s the answer | nothing; it returns inside the loop |
| 645 | index v - 1 | the destination already holds v | {nums[i], i + 1} at the first mismatch |
| 442 | index v - 1 | the destination already holds v | nums[i] for every mismatched index |
| 41 | index v - 1 | v is outside 1…n, or the destination already holds v | the first i where nums[i] != i + 1, else n + 1 |
Why two nested loops are still O(n)
The code has a while inside a for, which looks like O(n²) at a glance. It isn’t, and the reason is worth getting exactly right, because “it usually doesn’t run that many times” is not an argument.
Every swap puts at least one value at its final index, and a value at its final index is never moved again. The second half of that is the part to convince yourself of: a swap only ever targets dest when nums[dest] is not the value that belongs there, so a correctly placed slot is never chosen as a destination. There are only n values, so across the entire run there are at most n swaps — not n per outer step, n in total. The outer loop contributes another n iterations of constant work, and the second pass another n. The whole thing is bounded by about 3n operations.
With n up to 105, that’s a few hundred thousand operations. A hash set would also be O(n) time here, but it costs O(n) space and a lot of cache misses; cycle sort uses one integer of scratch space. That’s why 442 and 41 can demand constant auxiliary space and still be solvable.
One trace that covers three of the problems
Take nums = [3, 1, 3, 4, 2], with n = 5. The values should be 1 through 5; instead 3 appears twice and 5 is absent. Running the skeleton:
| Step | i | Array | nums[i] | dest | Action |
|---|---|---|---|---|---|
| 0 | — | [3,1,3,4,2] | — | — | start |
| 1 | 0 | [3,1,3,4,2] | 3 | 2 | slot 2 already holds a 3 → stop, move to the next i |
| 2 | 1 | [3,1,3,4,2] | 1 | 0 | slot 0 holds 3, not 1 → swap |
| 3 | 1 | [1,3,3,4,2] | 3 | 2 | slot 2 already holds a 3 → stop |
| 4 | 2 | [1,3,3,4,2] | 3 | — | already home |
| 5 | 3 | [1,3,3,4,2] | 4 | — | already home |
| 6 | 4 | [1,3,3,4,2] | 2 | 1 | slot 1 holds 3, not 2 → swap |
| 7 | 4 | [1,2,3,4,3] | 3 | 2 | slot 2 already holds a 3 → stop |
The array ends as [1, 2, 3, 4, 3]. Index 4 is the only slot holding the wrong value, and now read it three different ways:
- The index that’s wrong is 4, so
4 + 1 = 5is missing. That’s 448. - The value sitting there is 3, so 3 is the duplicate. That’s 442 and 287.
- Both at once,
{3, 5}. That’s 645.
The sort does all the work. The problems differ only in which half of the mismatch you print.
The six solutions
268. Missing Number (Easy)
The task: you get n distinct integers drawn from the range 0 through n. Exactly one value in that range is absent. Return it.
This is the only one of the six that is zero-indexed: value v belongs at index v, with no offset. The wrinkle is that the range has n + 1 possible values and only n slots, so one value has no home. If n itself is present it can never be placed, so leave it wherever it lands and let the second pass sort it out.
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = (int)nums.size();
for (int i = 0; i < n; ++i) {
// value v belongs at index v; n has no slot, so it stays put
while (nums[i] != i && nums[i] != n) {
int dest = nums[i];
swap(nums[i], nums[dest]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i) return i;
}
return n; // 0..n-1 all present, so n is the one missing
}
};No duplicate check is needed here, because the problem guarantees the values are distinct. That guarantee is doing real work — drop it and this loop can spin forever.
Worth knowing: 268 has two one-liners that don’t touch the array at all. XOR every index and every value together and the survivor is the answer, or subtract the array’s sum from n * (n + 1) / 2. Both are shorter than this. Cycle sort is here because it generalizes to the other five, which the tricks do not.
448. Find All Numbers Disappeared in an Array (Easy)
The task: an array of length n holds values from 1 to n, repeats allowed. Return every value in that range that never appears.
Now there can be several missing values, which means there are several duplicates, which means the break finally earns its place. Offset by one: value v belongs at index v - 1.
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = (int)nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] != i + 1) {
int dest = nums[i] - 1;
if (nums[dest] == nums[i]) break; // duplicate: its home is taken
swap(nums[i], nums[dest]);
}
}
vector<int> result;
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) result.push_back(i + 1);
}
return result;
}
};The second pass reports i + 1 — the value that should be at this index. Change that one expression to nums[i] and you have 442.
287. Find the Duplicate Number (Medium)
The task: an array of n + 1 integers holds values from 1 to n. Exactly one value repeats, possibly more than twice. Return it.
Here the moment that made us break in 448 is the answer. The first time a value finds its home already occupied by a copy of itself, that value is the duplicate, and you can return on the spot.
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = (int)nums.size(); // note: n is the array length, i.e. the problem's n + 1
for (int i = 0; i < n; ++i) {
while (nums[i] != i + 1) {
int dest = nums[i] - 1;
if (nums[dest] == nums[i]) return nums[i]; // home taken by a twin
swap(nums[i], nums[dest]);
}
}
return -1; // unreachable given the problem's guarantee
}
};Read this part before you use it in an interview. The problem says not to modify the array. Cycle sort modifies the array on every swap, so this is accepted by the judge and would be rejected by a careful interviewer. If the read-only constraint is real, the intended answer is Floyd’s cycle detection: treat each value as a pointer to the next index, and the duplicate is the entrance to the loop, found with a slow and a fast pointer in O(n) time and O(1) space without a single write. The other constraint-respecting option is binary search on the answer — count how many values are ≤ mid, in O(n log n).
Cycle sort is still worth writing here, because seeing 287 as “448 that returns early” is what makes the pattern stick. Just say out loud that it destroys the input.
645. Set Mismatch (Easy)
The task: a collection that should contain 1 through n has had one value overwritten by a copy of another. Given the resulting array, return the value that now appears twice together with the value that went missing.
Exactly the trace from earlier: one mismatched index, and both answers readable from it.
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int n = (int)nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] != i + 1) {
int dest = nums[i] - 1;
if (nums[dest] == nums[i]) break;
swap(nums[i], nums[dest]);
}
}
for (int i = 0; i < n; ++i) {
// the value squatting here is the duplicate; the value that should be
// here is the missing one
if (nums[i] != i + 1) return {nums[i], i + 1};
}
return {};
}
};One thing to notice about this problem’s constraints: they only promise the values are between 1 and 104, not between 1 and n. The guarantee that keeps dest in bounds comes from the prose — the collection was 1 through n before the corruption — not from the constraint list. Reading only the constraints, this code looks unsafe. It isn’t, but you should know which sentence you’re relying on.
442. Find All Duplicates in an Array (Medium)
The task: an array of length n holds values from 1 to n, each appearing once or twice. Return every value that appears twice, in linear time and constant space beyond the output.
Identical to 448 except for one expression in the second pass.
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int n = (int)nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] != i + 1) {
int dest = nums[i] - 1;
if (nums[dest] == nums[i]) break;
swap(nums[i], nums[dest]);
}
}
vector<int> result;
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) result.push_back(nums[i]); // 448 pushes i + 1 here
}
return result;
}
};The returned order won’t match the input order — this problem accepts any order, which is worth checking before you reach for this on a similar problem that doesn’t.
41. First Missing Positive (Hard)
The task: given an unsorted array of arbitrary integers, return the smallest positive integer that isn’t present, in O(n) time and O(1) space.
The whole reason this is rated Hard is that the input breaks the pattern’s precondition. Values can be negative, zero, or in the billions, and none of those have an index to go to. The unlock is one observation: the answer is always between 1 and n + 1. If all of 1…n are present the answer is n + 1, and otherwise it’s whichever of 1…n is missing. Nothing outside that window can ever be the answer, so anything outside it can be ignored where it lies. It’s still occupying a slot, but occupying a slot is exactly what “this index’s value is missing” looks like.
So it’s the same cycle sort with one extra stop condition — leave a value alone if it has no valid home:
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = (int)nums.size();
for (int i = 0; i < n; ++i) {
// long long: nums[i] can be INT_MIN, and INT_MIN - 1 overflows an int
long long dest = (long long)nums[i] - 1;
// stop if the value has no home (out of 1..n), or its home is already taken
while (dest >= 0 && dest < n && nums[dest] != nums[i]) {
swap(nums[i], nums[dest]);
dest = (long long)nums[i] - 1; // cast here too, not just above
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1; // 1..n all present
}
};The nums[dest] != nums[i] test quietly covers two cases at once. When dest == i the value is already home and the comparison is trivially false, so the loop exits. When dest != i and the values match, it’s a duplicate whose home is taken. One condition, both exits.
The long long is not decoration. This problem’s constraints allow the full signed 32-bit range, so nums[i] - 1 in plain int arithmetic is a signed overflow when the value is −2,147,483,648, which is undefined behaviour rather than a merely wrong number. The easy mistake is to cast on the first computation and forget the one inside the loop, where the value that just arrived from the swap can equally well be INT_MIN. Compiled with -fsanitize=undefined, the uncast version reports an overflow on an input as small as [2, INT_MIN, 1]. It happens to still return the right answer, because the wrap lands outside the bounds check, but that is luck rather than logic.
Edge cases and common bugs
- Time Limit Exceeded that looks like the wrong complexity — the duplicate guard is missing. Two copies of the same value swap into each other’s slots forever. If cycle sort hangs, this is the reason nine times out of ten.
- Wrong Answer with a half-sorted array —
ifwas written wherewhilebelongs. One swap per outer step places one value and abandons the one that just arrived at indexi. - Stale value after the swap — caching
int v = nums[i]before the swap and then continuing to usev. After the swap,nums[i]holds something different, and that’s the thing you now have to place. - Runtime Error on a small input — comparing
int iagainstnums.size(), which is unsigned.nums.size() - 1on an empty vector wraps to about 1.8×1019. Cast once at the top withint n = (int)nums.size();and compare againstneverywhere after that. - Silent off-by-one between the two families — 268 is zero-indexed (
vat indexv); the other five are one-indexed (vat indexv - 1). Copying one solution onto another problem without changing the offset produces a plausible wrong answer rather than a crash. - Undefined behaviour on LC 41 only —
nums[i] - 1inintarithmetic, in either of the two places it’s computed. The other five problems have positive-only values and don’t need the cast.
Inputs worth running by hand before submitting any of these: a single element, an array where every element is the same value, an array that’s already correct, and for 41, an array containing INT_MIN and INT_MAX.
Interview follow-ups
- “Can you do it without modifying the input?” — the honest answer is no, not with this pattern; cycle sort is destructive by definition. Pivot to Floyd’s cycle detection for 287, or to marking signs (negating
nums[abs(v) - 1]) for 442 and 448, which is still a mutation but a reversible one. - “What if a value can appear three or more times?” — the sort still terminates, but the second pass no longer enumerates every occurrence, only the ones left stranded. For full counts you need a counting pass and O(n) space.
- “What’s the space complexity really?” — O(1) auxiliary, and O(n) of the caller’s memory rearranged. Naming that trade-off unprompted is usually worth more than the solution itself.
- “Why not a hash set?” — same asymptotic time, O(n) space, and much worse constants. Cycle sort’s whole appeal is doing it in the array you were already given.
How to recognize it next time
Reach for cycle sort when all three of these are true: the values are integers confined to a range roughly the size of the array, the question is about which values are missing or repeated, and the problem asks for linear time with constant extra space. That third condition is usually the tell — it rules out sorting and it rules out a hash set, and there isn’t much left.
If the values can be arbitrary, as in 41, the pattern still applies as long as the answer is confined to a small range. Ignore everything that can’t be the answer, and the precondition comes back.
This walkthrough follows a session deck on cycle sort by Joseph Choi; the code here has been rewritten in a single consistent style and the explanations are my own. Every solution above was compiled and run against the problems’ sample cases and the edge cases listed, with the undefined-behaviour and address sanitizers on. If something here is wrong or there’s a cleaner way to say it, leave a comment. More problems: the LeetCode series.