Cyclic Sort

Problem Idea

You are given an array of size n containing numbers from 1 to n.

Your task:
Place every number at its correct index

---

Core Idea (Think Like This)

“If the current number is not at its correct position, swap it.”

“Keep doing this until every element is placed correctly.”

---

Step-by-Step Dry Run

Input:

[3, 5, 2, 1, 4]

---

Step 0: First Think

Value → Index
1 → 0
2 → 1
3 → 2
4 → 3
5 → 4

Formula:

correct index = value - 1

---

Start from index 0

[3, 5, 2, 1, 4]
 0  1  2  3  4
 ↑
 i

Current value is 3

correct index of 3 = 2

First Swap

swap(arr[0], arr[2])

[2, 5, 3, 1, 4]
 0  1  2  3  4
 ↑
 i 

Again Check

arr[i] = 2
correct index of 2 = 1

Second Swap

swap(arr[0], arr[1])

[5, 2, 3, 1, 4]
 0  1  2  3  4
 ↑
 i

Again Check

arr[i] = 5
correct index of 5 = 4

Third Swap

swap(arr[0], arr[4])

[4, 2, 3, 1, 5]
 0  1  2  3  4
 ↑
 i

Again Check

arr[i] = 4
correct index of 4 = 3

Third Swap

swap(arr[0], arr[3])

[1, 2, 3, 4, 5]
 0  1  2  3  4
 ↑
 i 

Now Check

arr[i] = 1
correct index of 1 = 0

Correct position

Now move forward:

i++

Continue

[1, 2, 3, 4, 5]
    ↑
    i = 1

2 is correct → move

3 is correct → move

4 is correct → move

5 is correct → move

---

Final Answer

[1, 2, 3, 4, 5]

---

What Just Happened?

At each step:

Check → Is number at correct index?

• No → swap

• Yes → move ahead

---

Most Important Rule

After swap → DO NOT move i

Why?

• Because new element came to index i

• It might also be wrong

---

Code

int i = 0;
while(i < n){
    int correct = arr[i] - 1;
    if(arr[i] != arr[correct]){
        swap(arr[i], arr[correct]);
    } else {
        i++;
    }
}

---

Complexity

• Time: O(n)

• Space: O(1)

---

Where This Pattern is Used

This is where things get interesting 👇

Same logic helps solve multiple problems:

---

1. Find All Duplicates in Array

int i = 0;
while (i < n) {
    int correct = arr[i] - 1;
    if (arr[i] != arr[correct]) {
        swap(arr[i], arr[correct]);
    } else {
        i++;
    }
}
vector<int> nums;
for (int i = 0; i < n; i++) {
   if(arr[i] != i + 1){
       nums.push_back(arr[i]);
   }
}

---

2. Find All Missing Numbers

int i = 0;
while (i < n) {
    int correct = arr[i] - 1;
    if (arr[i] != arr[correct]) {
        swap(arr[i], arr[correct]);
    } else {
        i++;
    }
}
vector<int> nums;
for (int i = 0; i < n; i++) {
   if(arr[i] != i + 1){
       nums.push_back(i + 1);
   }
}

---

3. Missing Number

int i = 0;
int n = nums.size();

while (i < n) {
    if (nums[i] < n && nums[i] != nums[nums[i]]) {
        swap(nums[i], nums[nums[i]]);
    } else {
        i++;
    }
}

for (int i = 0; i < n; i++) {
    if (nums[i] != i) {
        return i;
    }
}
return n;

---

4. First Missing Positive

int i = 0;
while (i < n) {
    if (arr[i] > 0 && arr[i] <= n) {
        int correct = arr[i] - 1;

        if (arr[i] != arr[correct]) {
            swap(arr[i], arr[correct]);
            continue;
        }
    }
    i++;
}

for (int i = 0; i < n; i++) {
    if (arr[i] != i + 1) {
        return i + 1;
    }
}
return n + 1;

---

Final Learning

At first, it looks like just swapping…

But actually:

It’s about placing elements at their correct index

Once you understand this:

You unlock 5–6 important interview problems