# Cyclic sort

## The Problem

[Leetcode 41. First Missing Positive(https://leetcode.com/problems/first-missing-positive/): Given an unsorted integer array, find the smallest missing positive integer.

```
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
```

Note: Your algorithm should run in O(n) time and uses constant extra space.

## The Solution

We clearly cannot use negative marking technique here as there is zero and negative numbers. Another way of modifying the input is *cyclic sort*. The idea is to keep swapping a number until it is mapping to correct index order. For instance, if we know the input contains from 1 to n, then we swap each number until 1 placed at 0-index, 2 at 1-index, etc.

```
def first_missing_positive(nums: List[int]) -> int:
for i, n in enumerate(nums):
while nums[i] != i+1:
if nums[i] <= 0 or nums[i] > len(nums) or nums[i] == nums[nums[i]-1]:
break
j = nums[i]-1
nums[i], nums[j] = nums[j], nums[i]
for i, n in enumerate(nums):
if i != n-1:
return i + 1
return len(nums) + 1
```

```
func firstMissingPositive(nums []int) int {
for i, _ := range nums {
for nums[i] != i+1 {
if nums[i] <= 0 || nums[i] > len(nums) || nums[i] == nums[nums[i]-1] {
break
}
j := nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
}
}
for i, n := range nums {
if i != n-1 {
return i + 1
}
}
return len(nums) + 1
}
```

## The Analysis

The complexity of cyclic sort is O(n), and can be proved using graph theory and mathematical induction.

Cyclic sort is a powerful algorithm, it is a O(n) sorting algorithm if **the array contains unique numbers from 1 to n**. In fact, other problems in previous sections can be solved with cyclic sort.

Similar problems:

## Leave a comment