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[] A) {
        int i = 0;
        while (i < A.length) {
            if (A[i] > 0 && A[i] != i + 1
                    && A[i] - 1 < A.length
                    && A[i] != A[A[i] - 1]) {
                swap(A, i, A[i] - 1);
            } else {
                i++;
            }
        }

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

        return A.length + 1;// if all values are in the correct position, then
        // we return the last one + 1
    }

    public void swap(int[] A, int i, int j) {// i and j are indices in array A
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

}

@@ -338,17 +338,20 @@
 e(int%5B%5D 
-A
+nums
 ) %7B%0A    
@@ -384,17 +384,20 @@
 le (i %3C 
-A
+nums
 .length)
@@ -415,17 +415,20 @@
     if (
-A
+nums
 %5Bi%5D %3E 0 
@@ -426,25 +426,28 @@
 s%5Bi%5D %3E 0 && 
-A
+nums
 %5Bi%5D != i + 1
@@ -466,25 +466,28 @@
          && 
-A
+nums
 %5Bi%5D - 1 %3C A.
@@ -484,17 +484,20 @@
 %5D - 1 %3C 
-A
+nums
 .length%0A
@@ -523,19 +523,28 @@
  && 
-A
+nums
 %5Bi%5D != 
-A%5BA
+nums%5Bnums
 %5Bi%5D 
@@ -576,15 +576,21 @@
 wap(
-A
+nums
 , i, 
-A
+nums
 %5Bi%5D 
@@ -690,17 +690,20 @@
  0; j %3C 
-A
+nums
 .length;
@@ -726,17 +726,20 @@
     if (
-A
+nums
 %5Bj%5D != j
@@ -816,17 +816,20 @@
  return 
-A
+nums
 .length 
@@ -832,18 +832,28 @@
 gth + 1;
-//
+%0A        /**
  if all 
@@ -896,19 +896,8 @@
 then
-%0A        //
  we 
@@ -912,19 +912,92 @@
 he l
-ast one + 1
+ength + 1.%0A         * This also takes care of corner case: %5B%5D, we return 1 for it.*/
 %0A   
@@ -1027,17 +1027,20 @@
 p(int%5B%5D 
-A
+nums
 , int i,
@@ -1052,41 +1052,8 @@
 j) %7B
-// i and j are indices in array A
 %0A   
@@ -1068,17 +1068,20 @@
  temp = 
-A
+nums
 %5Bi%5D;%0A   
@@ -1089,16 +1089,22 @@
     
-A
+nums
 %5Bi%5D = 
-A
+nums
 %5Bj%5D;
@@ -1116,9 +1116,12 @@
     
-A
+nums
 %5Bj%5D 

refactor 41