41. First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given[1,2,0]return3,
and[3,4,-1,1]return2.

Your algorithm should run inO(n) time and uses constant space.

Solution:

• nums[i] store i+1 value
  • if nums[i] == i+1
    • i++
  • if nums[i] != i+1
    • if dup, i++
    • if < 0, i++
    • if > nums.length, i++
• Traverse nums[i] to find i where nums[i] != i+1

448. Find All Numbers Disappeared in an Array

• nums[i] store i+1 value

442. Find All Duplicates in an Array

• nums[i] store i+1 value
• find dup
  • nums[i] > 0 ----> change to -nums[i], add to result list
  • nums[i] <0 ----> already in the dup list, continue