A very nice solution (from Ants Aasma @stackoverflow)


  • 32
    Y

    time complexity is O(N) and space complexity is O(1).

    Link: http://stackoverflow.com/questions/1586858/find-the-smallest-integer-not-in-a-list

    Posted by Ants Aasma on Oct 20 '09.

    The code is pasted here:

    #Pass 1, move every value to the position of its value
    for cursor in range(N): 
        target = array[cursor]
        while target < N and target != array[target]:
            new_target = array[target]
            array[target] = target
            target = new_target
    
    #Pass 2, find first location where the index doesn't match the value
    for cursor in range(N):
        if array[cursor] != cursor:
            return cursor
    return N

  • 10
    Y

    I did a small change (thanks for the down vote...):

    public class Solution {
        public int firstMissingPositive(int[] A) {
        // added line9 condition to avoid infinite loop
        // added line13, the i--, to check the swapped item. Or we failed to check all the numbers.
        // ref http://stackoverflow.com/questions/1586858/find-the-smallest-integer-not-in-a-list
                if (A.length == 0) return 1;
                for (int i = 0; i < A.length; i++) {
            		if (A[i] <= A.length && A[i] > 0 && A[i] != i+1) {
            		    if (A[A[i]-1] != A[i]) { //line 9
                			int tmp = A[A[i]-1];
                			A[A[i]-1] = A[i];
                			A[i] = tmp;
                			i--; //line 13
            		    }
            		}    		
            	}
            	for (int i = 0; i < A.length; i++) {
            		if (A[i] != i+1) return i+1;
            	}
            	return A.length+1;
        }
    }

  • 0
    J

    Submission Result: Time Limit Exceeded. I think it needs the condition "A[i]!=A[A[i]-1]" in line 8


  • 0
    V
    This post is deleted!

  • 0
    G

    This is a very smart solution. But can someone explain to me why this is an O(n) solution?
    It doesn't seem so obvious to me since there is a loop in the for loop. Thanks in advance.


  • 1
    G

    I think it is O(n) because of the target != array[target] condition. When the while loop goes more than one time, a new_target value is moved to its desired position. Then when the for loop gets to that position, the while loop does not execute (so we can consider this step takes no time). Therefore, in total, it is still O(n)


  • 0
    X

    The implementation here is kind of strange. Easy to cause ERROR. A while loop is better than using i++ i-- to keep loop. And what his code did is just move all the elements one position forward, say, A[0]=1,A[1]=2,.., drop 0, and numbers greater than n+1.


  • 0
    Y

    Am I the only person who think the solution is 3 pass?
    Because you will at most visit every element for three times.


  • 0
    H

    This code fails when first (or any) element is negative.(i.e. target becomes negative , array[target] gives index error)

    This is because while condition is missing a statement. to make sure that target >=0


  • 0
    H

    Well, you are not alone. Worst case is 3 pass. For instance, the following input:

    {[2,3,4,5,.....,n,1]}

    1. while loop passed through all of the array in the first iteration of the (first) for loop.
    2. First for loop iterates n times
    3. Second for loop iterates n times

  • 4
    H
    class Solution {
    public:
        int firstMissingPositive(int A[], int n) {
            for (int i = 0; i < n; ++i)
            {
                int num = A[i];
                while (num <= n && num > 0 && A[num - 1] != num)
                {
                    swap(A[num - 1], A[i]);
                    num = A[i];
                }
            }
            for (int i = 0; i < n; ++i)
            {
                if (A[i] != i + 1)
                {
                    return i + 1;
                }
            }
            return n + 1;
        }
    };
    

    Accepted C++ version.


  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at other posts in this thread.


  • 0
    N

    should add condition "target>=0"


  • 0
    L

    You're right, this code will fail on [3,4,-1,1], the swap result is [-1, 1,3, 4].


  • 1
    S

    I did a similar thing there. The algorithm is actually very simple and self explanatory. Its very similar to this excepting the implementation https://oj.leetcode.com/discuss/16657/share-my-32ms-o-n-o-1-solution
    The small change from the above python code is the shifting indices by 1 to match with 0-based.

    int firstMissingPositive(int A[], int n) {
            for(int i = 0; i < n; i ++)
            {
                int pick = A[i];
                while(pick > 0 && pick <= n && A[pick-1] != pick)
                {
                    int tmp = A[pick-1];
                    A[pick-1] = pick;
                    pick = tmp;
                }
            }
            for(int i = 0; i < n; i ++)
              if(A[i] != i+1) return i+1;
            return n+1;
        }
    

  • 1
    L

    What if there is duplicates in this array. In the while loop, if A[num - 1] == A[i] which != i + 1 there will be a infinite loop.


  • 0
    S

    I think this is more of a solution for the 'missing number' problem. https://leetcode.com/problems/missing-number/


  • 1
    K

    if the array contains very large numbers, won't this use up a lot of space?? Like if an array is [10000000,500000, 20000]


Log in to reply
 

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