Cyclic Sort

[darwinrlo]

Cyclic Sort

• 1 should go at position 0. 2 should go at position 1. And so on.
• Iterate through the array. At a position, look at the element. If it's not the right number for the position, swap it with the number at its correct position. Repeat until the number at the current position is the number that should be at this position.
• If no number is in the right place -- that is, every position contains the wrong number -- it'll take n-1 swaps to get everything right. So at most, n-1 swaps need to be made.
• In the worst case, every swap only puts one number in its rightful place. At some point, there are only two numbers out of place, in which case they will both be put in their rightful place with just one swap.

Example:

• [3, 1, 2]
• [2, 1, 3]
• [1, 2, 3]

[darwinrlo]

Find the Missing Number

[darwinrlo]

Find the Duplicate Number

• At some point, we will try to place a number and see that the correct number is already at the spot. We have found the duplicate.

[darwinrlo]

Find the Smallest Missing Positive Number

LeetCode: First Missing Positive Number

Input Characteristics

• There may be duplicates in the array.
• The elements are integers, i.e. negative, zero, or positive.
• The array is unsorted.

Scenarios

• The smallest number in the array is len(arr)+1.
  • The result should be 1.
• Otherwise,

Boundary Cases

• [] => 1
• [3] => 1
• [0] => 1
• [1] => 2

Algorithm

• Iterate through the array.
  • If the element is <= 0 or > len(n), then just skip over the element.
  • Otherwise, if the element is v, put the element at index v-1.
• Iterate through the array, returning the first number that is not at the correct spot. That is, at index i, if i+1 is not at the index, then return i+1.