Category Archives: sort

Cyclic Sort

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