2Brute2Best
🔥0

Cyclic Sort Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

When values are 1..n (or 0..n), each value has a "home" index. Swap values home; whatever is out of place is your answer.

3 sub-patterns · 9 questions

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?
A

What is this pattern?

When an array of size n holds values from a small fixed range like 1..n (or 0..n), every value has a natural home index: value v lives at index v − 1. Cyclic sort uses that fact to sort the array in O(N) with no extra memory, and then the mistakes in the array tell you the answer.

The move is: stand at index i, look at the value there, and swap it straight into its home. The value that comes back might also be out of place, so keep swapping at i until the value there is home, has no home (out of range), or its home already holds a copy of it (a duplicate). Then move to i + 1.

After placement, walk the array once and look for slots that don't hold their own value:

  • slot i without i + 1 → the value i + 1 is missing,
  • the value sitting in that wrong slot → it is a duplicate (a "squatter": its real home is already taken by its twin).

The array becomes its own hash set: "is k present?" is just "does slot k − 1 hold k?". When the array must not be changed, the same home idea still works as a linked list (i → nums[i]) with Floyd's cycle detection.

A cinema where every ticket has a seat number. People walk in and sit anywhere. You go seat by seat: if the person in this seat holds ticket 7, you send them to seat 7, and whoever was in seat 7 comes back to you. Keep going until this seat is right. In the end, empty seats are tickets nobody bought (missing), and someone standing because their seat is taken has a copied ticket (duplicate).

B

See it move

Cyclic sort on [4, 3, 2, 7, 8, 2, 3, 1]. Green = value at its home, orange = a duplicate whose home is taken, red = a wrong slot after placement.

Swap every value home, read the holesnums = [4, 3, 2, 7, 8, 2, 3, 1]step 1/25
nums
0
1
2
3
4
5
6
7
4
3
2
7
8
2
3
1
wants
0
1
2
3
4
5
6
7
1
2
3
4
5
6
7
8
State
n
8
i
—
swaps
0
Values are in 1..8: value v lives at index v − 1

Slot i should hold i + 1 (the "wants" row). Stand at each index and swap its value straight home until the value there can't go anywhere useful.

Sign marking on [4, 2, 4, 5, 2, 3, 1]. Blue = slot flipped negative (its value was seen), orange = slot found already flipped, so the current value repeats.

Mark seen values with a minus signnums = [4, 2, 4, 5, 2, 3, 1]step 1/9
nums
0
1
2
3
4
5
6
4
2
4
5
2
3
1
slot means
0
1
2
3
4
5
6
1?
2?
3?
4?
5?
6?
7?
repeats (in order)
[ ]
Slot x − 1 remembers whether x was seen

Values are 1..5 (two of them appear twice). Instead of moving values, flip the sign of nums[x − 1] the first time we meet x. The number stored there is still readable with abs().

C

How do I recognise it?

  • Values are in a range tied to the length: 1..n, 0..n, or 1..n with a couple of extras.

  • Find the missing number(s), the duplicate number(s), or both.

  • "Solve it in O(N) time and O(1) extra space". A hash set would be easy, so the extra-space limit is the real hint.

  • "Smallest missing positive": only values 1..n can matter, so the rest get ignored.

  • "Do not modify the array" on top of the range → the same home idea, read as a linked list (Floyd).

Looks like Cyclic Sort, but isn't

Find duplicates / missing values, but the values can be anything (−10⁹..10⁹)
→ Arrays & Hashing (set / map) or sorting

Cyclic sort needs every value to have a home inside the array. With arbitrary values there's no home index, so use a hash set (O(N) space) or sort (O(N log N)).

Exactly one number missing from 0..n (LC 268)
→ Sum or XOR also works

With exactly one unknown, n(n+1)/2 − sum or XOR of everything gives it in one read-only pass. Cyclic sort is the version that still works with several missing or duplicate values.

Find the duplicate, but you may not change the array
→ Floyd's cycle detection (Fast & Slow pointers)

Swapping and sign-marking both write into the array. Reading i → nums[i] as a linked list keeps the array untouched, and the duplicate is where the cycle starts.

Sort an array of arbitrary numbers
→ A normal sort

Cyclic sort only sorts because the values are exactly the indices shifted by one. Without that, a value has nowhere fixed to go.

D

How would I discover it from scratch?

Don't memorise “use cyclic sort”. Ask these questions in order — the pattern falls out.

For every candidate k in 1..n, scan the whole array to see if k is there (or how many times). That's n scans of n elements: O(N²).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Missing number

3 questions

Put every value that exists at its home. The slots left without their own value are the missing numbers.

02

Duplicate number

3 questions

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.

03

Missing + duplicate together

3 questions

One value appears twice and one is missing. After placement there is exactly one wrong slot, and it gives both answers: the duplicate is the value in it, and the missing number is its index + 1.

F

Don't mix these up

Cyclic sort vs Hash set

Are the values tied to the indices (1..n, 0..n)? Then the array is the set: cyclic sort or sign marking, O(1) space. Arbitrary values or extra space allowed → just use a set.

Cyclic sort vs Sign marking

Both use slot v − 1 as "v was seen". Cyclic sort moves values (good when you need the final layout, e.g. to find holes). Sign marking flags in one pass (good when the order you meet duplicates matters). Both modify the array.

Find All Duplicates (LC 442) vs Find the Duplicate Number (LC 287)

Same kind of input, different rules. LC 442 lets you modify the array → cyclic sort. LC 287 forbids it → Floyd's cycle (or binary search on the value). Reach for the swap and LC 287 is failed.

Missing Number (LC 268) vs Find All Numbers Disappeared (LC 448)

LC 268 is 0..n with one missing: home of v is v, and n has no home. LC 448 is 1..n with several missing: home of v is v − 1. Using the wrong home rule shifts every answer by one.

G

Code templates (C++)

Place every value home, then read the leftovers

The heart of the pattern. Swap while nums[nums[i] - 1] != nums[i], never while nums[i] != i + 1, which loops forever on duplicates. After placement, a wrong slot i means i + 1 is missing and nums[i] is a duplicate.

place-template.cpp
// Values 1..n (duplicates allowed): put each value at its home index v - 1,
// then every slot that doesn't hold its own value tells you something.
void placeAll(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        // keep swapping at i until the value here can't move anywhere useful
        while (nums[nums[i] - 1] != nums[i]) {       // NOT nums[i] != i + 1 (loops on duplicates)
            swap(nums[i], nums[nums[i] - 1]);        // one more value is home for good
        }
    }
}

// After placeAll: slot i holds i + 1, or it holds a squatter.
void readLeftovers(const vector<int>& nums, vector<int>& missing, vector<int>& duplicates) {
    for (int i = 0; i < (int)nums.size(); i++) {
        if (nums[i] != i + 1) {
            missing.push_back(i + 1);                // nobody brought value i + 1
            duplicates.push_back(nums[i]);           // its twin already owns its home
        }
    }
}

Values with no home (0..n, negatives, too big)

Before swapping, check that the value has a home. If it doesn't, leave it parked where it is. For 0..n the home of v is index v, and n has none. For First Missing Positive anything ≤ 0 or > n has none.

outsiders-template.cpp
// Some values have no home: skip them and leave them parked.
// Example: First Missing Positive. Only 1..n can matter; the answer is in 1..n+1.
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n &&       // has a home?
               nums[nums[i] - 1] != nums[i]) {       // home not already holding it?
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; i++)
        if (nums[i] != i + 1) return i + 1;          // first hole
    return n + 1;                                    // 1..n all present
}
// For values 0..n (Missing Number): home of v is index v, and v == n has no home.

Sign marking (one pass, keeps the order)

Instead of moving values, flip nums[|x| - 1] negative to record "x was seen". Always read with abs(), because the value might already be flipped. Because it's one left-to-right pass, you find each duplicate at its second occurrence.

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;
}

Read-only array: Floyd's cycle

Treat i → nums[i] as a linked list starting at index 0 (no value points to 0). Two indices point at the duplicate, so that's where the cycle starts. Phase 1: slow 1 step, fast 2 steps until they meet. Phase 2: one pointer back to 0, both 1 step, and they meet at the duplicate.

floyd-template.cpp
// n + 1 values in 1..n, array is READ-ONLY. Read i -> nums[i] as a linked list.
// Two indices point at the duplicate, so the duplicate is where the cycle starts.
int findDuplicate(const vector<int>& nums) {
    int slow = 0, fast = 0;                          // start at 0: no value points to 0
    do {
        slow = nums[slow];                           // 1 step
        fast = nums[nums[fast]];                     // 2 steps
    } while (slow != fast);                          // phase 1: meet inside the cycle
    slow = 0;                                        // phase 2: restart one from 0
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];                           // both 1 step now
    }
    return slow;                                     // cycle entry = duplicate
}
Next
Start with Missing number