public class Solution {
    public int firstMissingPositive(int[] A) {
        int n = A.length;
        for (int i=0; i<n; i++) {
            while (A[i] != i+1 && A[i]-1 >= 0 && A[i]-1 < n && A[i] != A[A[i]-1]) {
                swap(A, i, A[i]-1);
            }
        }
 
        for (int i=0; i<n; i++) {
            if (A[i] != i+1)    return i+1;
        }
        return n + 1;
    }
 
    void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}
 
// 3,4,-1,1
// -1,4,3,1
// -1,1,3,4
//
 

cHVibGljIGNsYXNzIFNvbHV0aW9uIHsKICAgIHB1YmxpYyBpbnQgZmlyc3RNaXNzaW5nUG9zaXRpdmUoaW50W10gQSkgewogICAgICAgIGludCBuID0gQS5sZW5ndGg7CiAgICAgICAgZm9yIChpbnQgaT0wOyBpPG47IGkrKykgewogICAgICAgICAgICB3aGlsZSAoQVtpXSAhPSBpKzEgJiYgQVtpXS0xID49IDAgJiYgQVtpXS0xIDwgbiAmJiBBW2ldICE9IEFbQVtpXS0xXSkgewogICAgICAgICAgICAgICAgc3dhcChBLCBpLCBBW2ldLTEpOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSB7CiAgICAgICAgICAgIGlmIChBW2ldICE9IGkrMSkgICAgcmV0dXJuIGkrMTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIG4gKyAxOwogICAgfQoKICAgIHZvaWQgc3dhcChpbnRbXSBBLCBpbnQgaSwgaW50IGopIHsKICAgICAgICBpbnQgdG1wID0gQVtpXTsKICAgICAgICBBW2ldID0gQVtqXTsKICAgICAgICBBW2pdID0gdG1wOwogICAgfQp9CgovLyAzLDQsLTEsMQovLyAtMSw0LDMsMQovLyAtMSwxLDMsNAovLwo=