# 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:**

```plaintext
[3, 5, 2, 1, 4]
```

* * *

### **Step 0: First Think**

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

Formula:

```plaintext
correct index = value - 1
```

* * *

**Start from index 0**

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

**Current value is 3**

```plaintext
correct index of 3 = 2
```

**First Swap**

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

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

**Again Check**

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

**Second Swap**

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

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

**Again Check**

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

**Third Swap**

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

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

**Again Check**

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

**Third Swap**

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

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

**Now Check**

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

**Correct position**

**Now move forward:**

```plaintext
i++
```

**Continue**

```plaintext
[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

```plaintext
[1, 2, 3, 4, 5]
```

* * *

### What Just Happened?

At each step:

```plaintext
Check → Is number at correct index?
```

*   No → swap
    
*   Yes → move ahead
    

* * *

### Most Important Rule

```plaintext
After swap → DO NOT move i
```

Why?

*   Because new element came to index `i`
    
*   It might also be wrong
    

* * *

### Code

```javascript
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

```javascript
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

```javascript
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

```javascript
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

```javascript
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