Cyclic Sort - kjingers/Grokking-Notes GitHub Wiki

Cyclic Sort

Iterate through the list. If the current number is not in it's correct index, then swap it with the number in it's correct index. Only move on to the next index once you have the correct number in the current index. If the number is missing for a given index, it will eventually get filled with the number n, since all other number will be swapped with their correct index. The number n is the only one that can't be.

def cyclic_sort(nums):

  i = 0
  while i < len(nums):
    # j is the index that the current num should be in
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1

  return nums

Find the Missing Number

Similar to above. Instead, if the number's correct index isn't in nums, then go to next number. After sorting, iterate through and return the first index where the number doesn't correspond to the index.

def cyclic_sort(nums):

  i = 0
  while i < len(nums):
    # j is the index that the current num should be in
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1

  return nums

Find All Missing Numbers

Similar to "Find Missing Number" above. Except we add all missing numbers. Cyclic sort works, because if the number for a given index doesn't exist, we eventually iterate to the next index once the number in the current index is a duplicate (nums[i] == nums[j])

def find_missing_numbers(nums):
  missingNumbers = []
  i = 0
  n = len(nums)

  print(nums)
  while i < n:
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1
  print(nums)

  for i in range(n):
    if i != (nums[i] - 1):
      missingNumbers.append(i + 1)

  return missingNumbers

Find Duplicate Number

In this problem, there is only one duplicate number, but it can be duplicated multiple times. So, we follow above, but can return if we cannot get the correct number in the current index (nums[i] == nums[j], but nums[i] - 1 != i

To solve without modifying the input array and O(1) space, we can use fast and slow pointers too.

def find_duplicate(nums):
  i = 0

  while i < len(nums):
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]
    elif i != (nums[i] - 1):
      return nums[i]
    else:
      i += 1

Find All Duplicate Numbers

Very similar to above. Except after sorting, we loop though and append any number that isn't in the correct index.

def find_all_duplicates(nums):
  duplicateNumbers = []
  i = 0

  while i < len(nums):
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1

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

  return duplicateNumbers

Finding the Corrupt Pair

Very similar to above. We do the same thing, and return but the duplicate number and index (which is the number that got corrupted)

def find_corrupt_numbers(nums):
  i = 0

  while i < len(nums):
    j = nums[i] - 1
    if nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1

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

  return []

Find the Smallest Missing Positive Number

Similar to above. We want to put positive numbers (1, 2, 3...) into indices: 0, 1, 2.... So that means, we must skip numbers that are <= 0, or numbers that are >= len(nums)

def find_first_smallest_missing_positive(nums):
  i = 0

  while i < len(nums):
    j = nums[i] - 1
    if (j < 0) or (j >= len(nums)):
      i += 1
    elif nums[i] != nums[j]:
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1

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

Find First K Missing Positive Numbers

Similar to above. The tricky things is we need to keep track of numbers that are >= len(nums). We cannot sort these to the correct index, but they cannot be counted as "missing". So, once we sort as normal, we iterate through and add to missing numbers array, but also adding the numbers in those indices to a set. Once finished adding all the missing numbers from our array, we iterate from len(n) + 1 and add to missingNums array if the number doesn't exist in our extraNums set.

def find_first_k_missing_positive(nums, k):
  missingNumbers = []
  i = 0
  n = len(nums)

  while i < n:
    j = nums[i] - 1
    if (j >= 0) and (j < n) and (nums[i] != nums[j]):
      nums[i], nums[j] = nums[j], nums[i]
    else:
      i += 1

  extraNums = set()

  for i in range(n):
    if nums[i] != (i + 1):
      if len(missingNumbers) < k:
        missingNumbers.append(i + 1)
        extraNums.add(nums[i])

  i = 1
  while len(missingNumbers) < k:
    candidateNumber = i + n
    if candidateNumber not in extraNums:
      missingNumbers.append(candidateNumber)
    i += 1
⚠️ **GitHub.com Fallback** ⚠️