Cycle Sort §

---

Cycle Sort is a linear time constant space sorting algorithm that requires moving numbers into their range adjusted indices in an array. Then, a linear search through the array can reveal the first number missing in the range.

Explore §

Is this at the right index?                 

   4 2 3 1                         2 3 2 4     5 1 2 3
   n -> put it where it belongs.   3 2 2 4     n -> impossible index -> next
   1 2 3 4                         2 2 3 4     5 1 2 3
   y y y y                         2 2 3 4     1 5 2 3
   -> linear search for soln                   1 2 5 3
                                               1 2 3 5 -> linear search

Python Solution §

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0  # swap each element encountered to its proper index
        while i < n:
            dest = nums[i] - 1  # handles duplicates vs nums[i] != i+1
            # is nums[i] where it goes? vs is nums[i] == i+1?
            if 0 < nums[i] <= n and nums[i] != nums[dest]:
                nums[i], nums[dest] = nums[dest], nums[i]
            else:
                i += 1
 
        for i in range(n):  # return first missing integer
            if nums[i] != i + 1:
                return i + 1
 
        # if array contains 1...n then n+1 is the first missing integer
        return n + 1

Complexity Analysis §

We make at most n swaps & use constant additional memory → O(n) time & O(1) space.

C++ Solution §

  TODO: c++ solution