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 static class Solution1 {
    /**
     * Time: O(n) Space: O(1)
     *
     * Idea: put every number in its right position, e.g. put 5 in nums[4].
     */
    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;
    }

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

@@ -33,257 +33,8 @@
 s;%0A%0A
-/**%0A *41. First Missing Positive%0A *%0A *Given an unsorted integer array, find the first missing positive integer.%0A%0A For example,%0A Given %5B1,2,0%5D return 3,%0A and %5B3,4,-1,1%5D return 2.%0A%0A Your algorithm should run in O(n) time and uses constant space.%0A */%0A%0A
 publ
@@ -51,16 +51,18 @@
 41 %7B%0A%0A  
+ 
+ 
 public s
@@ -85,16 +85,20 @@
 tion1 %7B%0A
+    
     /**%0A
@@ -102,16 +102,20 @@
 **%0A     
+  
+  
 * Time: 
@@ -139,11 +139,8 @@
     
- *%0A
     
@@ -220,11 +220,19 @@
     
+ 
-*/%0A
+   */%0A    
     
@@ -273,24 +273,30 @@
 t%5B%5D nums) %7B%0A
+      
       int i 
@@ -300,16 +300,22 @@
  i = 0;%0A
+      
       wh
@@ -338,32 +338,40 @@
 ngth) %7B%0A        
+       
+ 
 if (nums%5Bi%5D %3E 0 
@@ -462,16 +462,38 @@
     
-- 1%5D) %7B%0A
+            - 1%5D) %7B%0A          
     
@@ -534,16 +534,24 @@
         
+   
+     
 %7D else %7B
@@ -561,16 +561,26 @@
         
+         
+ 
 i++;%0A   
@@ -580,35 +580,55 @@
 ++;%0A        
+      
-%7D%0A
+  %7D%0A    
       
+  
 %7D%0A%0A
+      
       for (i
@@ -657,24 +657,32 @@
 gth; j++) %7B%0A
+        
         if (
@@ -697,24 +697,34 @@
 != j + 1) %7B%0A
+          
           re
@@ -747,19 +747,39 @@
     
-%7D%0A
+        %7D%0A     
       
+ 
 %7D%0A%0A
+      
     
@@ -800,24 +800,28 @@
 length + 1;%0A
+    
     %7D%0A%0A    v
@@ -819,16 +819,20 @@
  %7D%0A%0A    
+  
+  
 void swa
@@ -857,24 +857,30 @@
 i, int j) %7B%0A
+      
       int te
@@ -895,24 +895,30 @@
 s%5Bi%5D;%0A      
+     
+ 
 nums%5Bi%5D = nu
@@ -924,16 +924,22 @@
 ums%5Bj%5D;%0A
+      
       nu
@@ -956,16 +956,22 @@
 mp;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 41