O(n) time, O(1) space C++


  • 18
    L

    Idea is to swap each positive integer you encounter to its "rightful" place at index (x-1) where x is the integer. It's O(n) because you visit each integer in at most 2 unique loop iterations.

    class Solution {
    public:
        int firstMissingPositive(int A[], int n) {
            int i,j;
            for(i=0;i<n;i++){
                int cur=A[i];
                // if in place or non-pos or out of bounds, skip.
                if(cur==i+1||cur<=0||cur>n)continue;
                swap(A[i],A[cur-1]);
                // if not the same, then reprocess it.
                if(A[i]!=A[cur-1])
                    i--;
            }
            
            for(i=0;i<n;i++)
                if(A[i]!=i+1) 
                    return i+1;
            return n+1;
        }
    };

  • 0
    F

    Cool idea... Initially I thought that due to if(A[i]!=A[cur-1]) i--; it would take O(n^2) time.. but then realized...


  • 0
    R

    Great Idea!!!!!!!!!1


  • 0
    Y

    I think the second if statement in the first for loop should be if(A[i] != A[A[i]-1]), since cur is dirty after you swap A[i] and A[cur-1].


  • 0
    L

    We still want to compare using the old value of cur


  • 0
    Y

    I'm kind of confused. If the input is [3,5,1,4,2], in first iteration, i = 0, cur = 3, swap A[0] and A[2]. So A becomes [1,5,3,4,2]. Now A[0] is also in right position. But cur is still 3. The second if statement fails and thus decrease i, which is not necessary. Can you explain why you still need the old value?


  • 0
    L

    How about you shorten the code first and check whether it can pass the tests? If so then post it as an answer here


  • 0
    Y

    I misunderstood your idea. You are checking whether the two numbers you just swapped are the same. BTW, if you change the second if statement to if(A[i] != A[A[i]-1]), it still passes all the tests. This statement checks whether A[i] is put in the right position, so it does not affect the correctness of the algorithm.


  • 0
    S

    if the test case is [1,1], you logic will stuck at 1 on the second place. It will keep going back since the if(A[i]!=A[cur-1]) i--; So maybe you should add a judgement on this .


  • 0
    L

    @stanley are u sure? Look carefully


  • 0
    X
    This post is deleted!

  • 0

    This is one of that, "So simple but not everybody can come up with" type of solution. Impressive.
    O(n) Time, O(1) space. Elegant and concise. Thanks for sharing.


  • 0
    G

    if there are some negative numbers at the begining of A,for example -4,-3,1,for(i=0;i<n;i++) if(A[i]!=i+1) return i+1;will return 3,but it's wrong


Log in to reply
 

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