"""Leetcode 41. First Missing Positive
Hard

URL: https://leetcode.com/problems/first-missing-positive/

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

Example 1:
Input: [1,2,0]
Output: 3

Example 2:
Input: [3,4,-1,1]
Output: 2

Example 3:
Input: [7,8,9,11,12]
Output: 1

Note:
Your algorithm should run in O(n) time and uses constant extra space.
"""

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int

        Time complexity: O(n).
        Space complexity: O(1).
        """
        n = len(nums)

        for i in range(n):
            # Keep swapping old & new nums[i]'s to their correct positions.
            while nums[i] > 0 and nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                # If nums[i] = k, swap it and nums[k - 1] at correct position k - 1.
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

        # Check each updated elements in nums with true positive integer.
        for i in range(n):
            if i + 1 != nums[i]:
                return i + 1

        # If all elements in nums are correct, return the last one plus one.
        return n + 1


def main():
    # Ans: 3
    nums = [1,2,0]
    print Solution().firstMissingPositive(nums)

    # Ans: 2
    nums = [3,4,-1,1]
    print Solution().firstMissingPositive(nums)

    # Ans: 1
    nums = [7,8,9,11,12]
    print Solution().firstMissingPositive(nums)

    # Ans: 1
    nums = []
    print Solution().firstMissingPositive(nums)

    # Ans: 2
    nums = [1]
    print Solution().firstMissingPositive(nums)

    # Ans: 3
    nums = [-1,4,2,1,9,10]
    print Solution().firstMissingPositive(nums)


if __name__ == '__main__':
    main()

@@ -391,16 +391,32 @@
 Solution
+SwapToCorrectPos
 (object)
@@ -632,64 +632,58 @@
     
-for i in range(n):%0A            # Keep swapping old & new
+# Iterate through all positions, continue swapping
  num
@@ -691,16 +691,26 @@
 %5Bi%5D's to
+%0A        #
  their c
@@ -724,16 +724,25 @@
 position
+ (i + 1)'
 s.%0A     
@@ -748,33 +748,48 @@
     
-    while nums%5Bi%5D %3E 0 and
+for i in range(n):%0A            while 0 %3C
  num
@@ -836,93 +836,8 @@
 1%5D:%0A
-                # If nums%5Bi%5D = k, swap it and nums%5Bk - 1%5D at correct position k - 1.%0A
     
@@ -1183,27 +1183,30 @@
 in():%0A    # 
-Ans
+Output
 : 3%0A    nums
@@ -1226,32 +1226,48 @@
   print Solution
+SwapToCorrectPos
 ().firstMissingP
@@ -1279,35 +1279,38 @@
 ve(nums)%0A%0A    # 
-Ans
+Output
 : 2%0A    nums = %5B
@@ -1329,32 +1329,48 @@
   print Solution
+SwapToCorrectPos
 ().firstMissingP
@@ -1382,35 +1382,38 @@
 ve(nums)%0A%0A    # 
-Ans
+Output
 : 1%0A    nums = %5B
@@ -1435,32 +1435,48 @@
   print Solution
+SwapToCorrectPos
 ().firstMissingP
@@ -1496,19 +1496,22 @@
 %0A%0A    # 
-Ans
+Output
 : 1%0A    
@@ -1530,32 +1530,48 @@
   print Solution
+SwapToCorrectPos
 ().firstMissingP
@@ -1591,19 +1591,22 @@
 %0A%0A    # 
-Ans
+Output
 : 2%0A    
@@ -1626,32 +1626,48 @@
   print Solution
+SwapToCorrectPos
 ().firstMissingP
@@ -1691,11 +1691,14 @@
   # 
-Ans
+Output
 : 3%0A
@@ -1742,16 +1742,32 @@
 Solution
+SwapToCorrectPos
 ().first

Revise comments