# 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.


class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        for index in xrange(n):
            element = nums[index]
            while True:
                if element <= 0 or element > n or element == nums[element - 1]:
                    break
                nums[element - 1], element = element, nums[element - 1]
        for index in xrange(n):
            if nums[index] != index + 1:
                return index + 1
        return n + 1

# Note:
# The idea is to place the element to element-1th position in the array, ignoring all the elements less than 1,
# greater than n. Continue this for replaced element until it violates the condition.
