package com.fishercoder.solutions;

/**
 *41. First Missing Positive
 * 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.
 */

public class _41 {

    public int firstMissingPositive(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] > 0 && nums[i] != i + 1
                    && nums[i] - 1 < nums.length
                    && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            } else {
                i++;
            }
        }

        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != j + 1) {
                return j + 1;
            }
        }

        return nums.length + 1;
        /** if all values are in the correct position, then we return the length + 1.
         * This also takes care of corner case: [], we return 1 for it.*/
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

@@ -64,17 +64,16 @@
 itive%0A *
- 
 Given an
@@ -295,16 +295,56 @@
  _41 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -389,24 +389,28 @@
 ) %7B%0A        
+    
 int i = 0;%0A 
@@ -416,16 +416,20 @@
         
+ 
+   
 while (i
@@ -442,24 +442,28 @@
 s.length) %7B%0A
+    
             
@@ -510,32 +510,36 @@
                 
+  
+  
 && nums%5Bi%5D - 1 %3C
@@ -551,16 +551,20 @@
 .length%0A
+    
         
@@ -626,16 +626,20 @@
         
+   
+ 
 swap(num
@@ -670,16 +670,20 @@
         
+    
 %7D else %7B
@@ -699,16 +699,20 @@
         
+   
+ 
 i++;%0A   
@@ -712,34 +712,42 @@
 ++;%0A            
-%7D%0A
+    %7D%0A    
         %7D%0A%0A     
@@ -749,16 +749,20 @@
         
+    
 for (int
@@ -797,32 +797,36 @@
 ) %7B%0A            
+    
 if (nums%5Bj%5D != j
@@ -845,24 +845,28 @@
             
+ 
+   
 return j + 1
@@ -879,26 +879,32 @@
         
-%7D%0A
+    %7D%0A  
         
 %7D%0A%0A     
@@ -887,35 +887,41 @@
     %7D%0A          
+  
 %7D%0A%0A
+    
         return n
@@ -944,16 +944,20 @@
         
+   
+ 
 /** if a
@@ -1035,16 +1035,20 @@
         
+    
 * This a
@@ -1104,23 +1104,31 @@
 r it.*/%0A
+    
     %7D%0A%0A
+    
     publ
@@ -1172,24 +1172,28 @@
 ) %7B%0A        
+    
 int temp = n
@@ -1204,24 +1204,28 @@
 i%5D;%0A        
+ 
+   
 nums%5Bi%5D = nu
@@ -1235,24 +1235,28 @@
 j%5D;%0A        
+    
 nums%5Bj%5D = te
@@ -1259,16 +1259,26 @@
 = temp;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 41