Leetcode pattern: Cyclic Sort

How it works?

If current index X but value Y (not same), we swap it with index Y

Let's say we have the array below:

[1,4,3,2,0]

Our current index is 0 but value is 1, we swap it with index 1

[4,1,3,2,0]

We check again, current index is 0 but value is  4, we swap with index 4

[0,1,3,2,4]

Now index 0 has value 0, we proceed to index 1.

Index 1 also has value 1, we proceed to index 2.

Index 2 has value 3, we swap with index 3.

[0,1,2,3,4]

Index 2 now has value 2. We proceed to index 3 which has value 3, we proceed to index 4 which has value 4. The array is now sorted.

Pseudocode

def cyclic_sort(nums):
    index = 0
    # iterate through the array
    while index < len(nums):
        value = nums[index]
        if index != nums[index]:
        	# Swap
            nums[index], nums[value] = nums[value], nums[index]
        else:
            index += 1
    return

When use?

Tips from fellow Redditors:

You have array of size N with numbers in range 0-N shuffled. Cyclic sort will sort them in O(n)

When you need to find duplicates in a [1, n] range you can use cyclic sort or what I like to call cyclic mark to mark the items then if you see them again you can add to your answer array.

How to study

1) Read this article by Emre Bolat, follow along to solve Leetcode #268,  image in the article helpful for understanding the solution.

Pattern 1: If value range more than number of elements (Missing Number)

268. Missing Number

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        index = 0

        while index < len(nums):
            value = nums[index]
            # first condition: if it is the number n we leave it
            # second condition: index not same as value
            if nums[index] < len(nums) and nums[index] != index:
                # Swap
                nums[index], nums[value] = nums[value], nums[index]
            else:
                index += 1
        
        # find value that is not same as index
        for idx in range(len(nums)):
            if nums[idx] != idx:
                return idx
        
        # if all values match index, then the missing number is at the end of range
        return len(nums)

2) Solve Leetcode #287

Pattern 2: If value range same as number of elements (Duplicate Number)

287. Find the Duplicate Number

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        index = 0

        while index < len(nums):
        	# first condition: index not same as value
            # second condition: the current value and the \ 
			# value that we want to swap are not the same (duplicates)
            value = nums[index]
            if ((value-1) != index) and (value != nums[value-1]):
                #swap
                nums[index], nums[value-1] = nums[value-1], nums[index]
            else:
                index += 1
            
        for i in range(len(nums)):
            if nums[i] != i+1:
                return nums[i]

Problems solved using this pattern

442. Find All Duplicates in an Array
448. Find All Numbers Disappeared in an Array