Cyclic sort

1 minute read

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:

Find first k natural numbers missing in given array

Updated:

Leave a comment