Skill Set - Cyclic Sort

Skills for tackling LeetCode problems - Cyclic Sort.

Problem statement: You are given an unsorted array containing n numbers taken from the range 1 to n. The array can have duplicates, which means that some numbers will be missing. Find all the missing numbers.

As we know the range is from 1 to n, we can place each number at it correct index, e.g. placing 1 to index 0, placing 2 to index 1 and so on. After this sorting, we can iterate the array to find all indices missing the correct numbers.

1. Cyclic Sort

We are given an array containing n object. Each object, when created, was assigned a unique number from the range 1 to n based on their creation sequence. This means that the object with sequence number 3 was created just before the object with sequence number 4. Write a function to sort the objects in-place on their creation sequence number in O(N) and without using any extra space. For simplicity, let’s assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.

# Iterate the array one number at a time. If the current number is not at the correct index, swap it with the number at its correct index.
# Time complexity O(N). Space complexity O(1).
def cyclic_sort(nums):
    for i in range(len(nums)):
        while nums[i] != nums[nums[i] - 1]:
            index = nums[i] - 1
            nums[i], nums[index] = nums[index], nums[i]
    return nums

2. Find the Missing Number

We are given an array containing n distinct numbers taken from the range 0 to n. Since the array has only n numbers out of the total n+1 numbers, find the missing number.

# Iterate the array, cyclic sort, find the index which does not have the correct number
# Time complexity O(N). Space complexity O(1).
def find_missing_number(nums):
    for i in range(len(nums)):
        index = nums[i]
        while nums[i] < len(nums) and nums[i] != nums[nums[i]]:
            index = nums[i]
            nums[i], nums[index] = nums[index], nums[i]

    for i in range(len(nums)): # find the 1st missing number
        if nums[i] != i: return i
    return len(nums)

3. Find all Missing Numbers

We are given an unsorted array containing numbers taken from the range 1 to n. The array can have duplicate, which means some numbers will be missing. Find all those missing numbers.

# Time complexity O(N). Space complexity O(1).
def find_missing_numbers(nums):
    # Sort
    for i in range(len(nums)):
        while nums[i] != nums[nums[i] - 1]:
            index = nums[i] - 1
            nums[i], nums[index] = nums[index], nums[i]
        
    result = [] # missing value

    for i in range(len(nums)):
        if nums[i] != i + 1:
            result.append(i + 1)
    return result

4. Find the Duplicate Number

We are given an unsorted array containing n+1 numbers taken from the range 1 to n. The array has only one duplicate but it can be repeated multiple times. Find that duplicate number without using any extra space. You are allowed to modify the input array.

# Time complexity O(N). Space complexity O(1).
def find_duplicate(nums):
    for i in range(len(nums)):
        while nums[i] != i+1:
            index = nums[i] - 1
            if nums[i] != nums[index]: # not duplicate
                index = nums[i] - 1
                nums[i], nums[index] = nums[index], nums[i]
            else: # duplicate
                return nums[i]

    return -1

5. Find all Duplicate Number

We are given an unsorted array containing n numbers taken from the range 1 to n. The array has some numbers appearing twice, find all these duplicate numbers without using any extra space.

# Time complexity O(N). Space complexity O(1).
def find_all_duplicates(nums):
    for i in range(len(nums)):
        index = nums[i] - 1
        while nums[i] != nums[index]: # sort
            index = nums[i] - 1
            nums[i],nums[index] = nums[index], nums[i]

    result = []
    for i in range(len(nums)):
        if nums[i] != i + 1: # find duplicate
            result.append(nums[i])
    return result