Blog

Cyclic Sort

Time Complexcity:  O(n)
Space Complexity: O(1)
for i in 0 to n-1:
    while nums[i] is not the value expected at the spot:
        let d = destination index to which nums[i] should be sent
        nums[i], nums[d] = nums[d], nums[i]

def cyclic_sort(nums):
    for i in range(len(nums)):
        destinationIndex = nums[i] - 1
        while nums[i] != i + 1: 
            nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]
            destinationIndex = nums[i] - 1
    return nums

print(cyclic_sort([3, 1, 5, 4, 2]))
print(cyclic_sort([2, 6, 4, 3, 1, 5]))
print(cyclic_sort([1, 5, 6, 4, 3, 2]))

Given an array nums containing n distinct numbers in the range [0, n],
return the only number in the range that is missing from the array.
def missingNumber(nums):
   for i in range(len(nums)): 
       destinationIndex = nums[i]
       while 0 <= destinationIndex < len(nums) and nums[i] != i: # while value is not the expected value            
            nums[destinationIndex], nums[i] = nums[i], nums[destinationIndex]
            destinationIndex = nums[i] 

   for i in range(len(nums)):
      if nums[i] != i:
         return i
   return len(nums)

Given an unsorted integer array nums, find the smallest missing positive integer.

def firstMissingPositive(nums):
    # nums = [1,2,3,4...]
    # nums[nums[i] - 1] = nums[i]
    for i in range(len(nums)):
    destinationIndex = nums[i] - 1
    while 0 <= destinationIndex < len(nums) and nums[i] != i + 1:
        nums[destinationIndex], nums[i] = nums[i], nums[destinationIndex]
        destinationIndex = nums[i] - 1

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

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
Time Complexcity:  O(n)
Space Complexity: O(1)

def findDuplicate(nums):
    for i in range(len(nums)):
        destinationIndex = nums[i] - 1
        while 0 <= destinationIndex < len(nums) and nums[i] != i + 1:
        if nums[destinationIndex] == destinationIndex + 1:
            break
        nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]
        destinationIndex = nums[i] - 1

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

We are given an unsorted array containing numbers taken from the range 1 to ‘n’.
The array can have duplicates, find all duplicates.

def find_all_duplicates(nums):
  for i in range(len(nums)):
    destinationIndex = nums[i] - 1
    while nums[i] != i + 1:
      if nums[destinationIndex] == destinationIndex +1:
        break
      nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]  # swap
      destinationIndex = nums[i] - 1
  duplicateNumbers = []
  for i in range(len(nums)):
    if nums[i] != i + 1:
      duplicateNumbers.append(nums[i])
return duplicateNumbers

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

def find_missing_numbers(nums):
    missingNumbers = []
    for i in range(len(nums)):
        destinationIndex = nums[i] -1
        while nums[i] != i + 1:
            if nums[destinationIndex] == destinationIndex + 1:
                break
            nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]
            destinationIndex = nums[i] - 1
    for i in range(len(nums)):
        if nums[i] != i + 1:
            missingNumbers.append(i + 1)
    return missingNumbers

We are given an unsorted array containing ‘n’ numbers taken from the range 1 to ‘n’. 
The array originally contained all the numbers from 1 to ‘n’, but due to a data error, 
one of the numbers got duplicated which also resulted in one number going missing. 
Find both these numbers.

def find_corrupt_numbers(nums):
    missingpair = []
    for i in range(len(nums)):
        destinationIndex = nums[i] - 1
        while nums[i] != i + 1:
            if nums[destinationIndex] == destinationIndex + 1:
                break
            nums[destinationIndex], nums[i] = nums[i] , nums[destinationIndex]
            destinationIndex = nums[i] - 1

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

Given an unsorted array containing numbers and a number ‘k’,
find the first ‘k’ missing positive numbers in the array.

def find_first_k_missing_positive(nums, k):
    for i in range(len(nums)):
        destinationIndex = nums[i] - 1
        while nums[i] != i + 1:
            if not 0 <= destinationIndex < len(nums) or nums[destinationIndex] == destinationIndex + 1:
                break
            nums[i], nums[destinationIndex] = nums[destinationIndex], nums[i]
            destinationIndex = nums[i] - 1
    missingNums = []

    for i in range(len(nums)):
        if nums[i] != i + 1:
            missingNums.append(i+1)
        if len(missingNums) >= k:
            break

    i = 1
    while len(missingNums) < k:
        missingNums.append(nums[-1] + i)
        i += 1
    return missingNums