LeetCode Q41: First Missing Positive (hard)

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

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

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

The idea is simple. Since O(n) time and O(1) space is required, basically ask us to solve the problem by scanning the array only. Since all number are either negative numbers or continues positive integers. Once we know the min and max of the array, we are suppose to know the correct position of each element in the array. So, we then could keep swapping the element to find their correct position. The algorithm will stop once all elements are processed.