Finally Came Up With a O(n) constant space solution using the array itself (Java Solution)


  • 0
    S

    I take use of the array itself.

    First, let's consider one thing: if everything's fine and in order, we want the array to be like [1,2,3,4,5,-1,0,-2]. That is everything positive is right at the begin part and everything we don't care is at the end. Since negative integer and zero are the same for us in this particular problem, I transform them into X. Then it become [1,2,3,4,5,X,X,X]. If some integer miss, we want the array to keep its well-formed shape as [1,X,2,3,4,5,X,X,X], then we can go through the entire array to find where the first X appear. If X not show up, that's good. that means no integer missing, output the maximum+1.

    Then, I'll illustrate how to put the original array into [1,X,3,4,5,X,X,X] form.
    Here I use X=-1. And I'll keep finding the correct position an integer should appear and replace it and set the it's position to -1.
    I take three pass.

    1st pass through the array.

    (1) Note down how many positive integers are there.

    (2) Set all non-positive number to -1

    2nd pass through the array. !!!

    First check if current integer buffer is -1, if yes, that means we need to deal with the replaced integer we find last time. If not, that means the replaced integer is invalid. We can continue going through the array.
    Only when the current position has the correct integer, do we continue.

    3rd pass through the array.

    Now the array has been transformed into [1,X,3,4,5,X,X]. Easily get the result.

    public class Solution {
        public int firstMissingPositive(int[] A) {
            int totalPositive = 0;
            int temp = -1;
            int median;
            for(int i = 0;i < A.length;i++){
                if(A[i] > 0)
                    totalPositive++;
                else
                    A[i] = -1;
            }
            for(int i = 0;i < A.length;i++){
                if(temp == -1){
                    if(A[i] > 0){
                        // if the integer is larger than totalPositive, means it's invalid
                        if(A[i] > totalPositive){
                            A[i] = -1;
                        }else{
                            // find the correct position for a valid integer and set buffer
                            if(A[A[i]-1] != A[i]){
                                temp = A[A[i]-1];
                                A[A[i]-1] = A[i];
                                A[i] = -1;
                            }else{
                                if(A[i]-1 != i)
                                    A[i] = -1;
                                temp = -1;
                            }
                        }
                    }
                }else{
                    // deal with the buffer's valid integer
                    if(temp <= totalPositive){
                        if(A[temp-1] != temp){
                            median = A[temp-1];
                            A[temp-1] = temp;
                            temp = median;
                        }else{
                            temp = -1;
                        }
                    }else{
                        temp = -1;
                    }
                    i--;
                }
            }
            
            for(int i = 0;i < A.length;i++)
                if(A[i] == -1)
                    return i+1;
            return totalPositive+1;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.