leetcode Question 29: First Missing Positive

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.


If we can use another array flag, we can assign flag[A[i]-1] = A[i] to present its occurrence.And get the first element from flag that the flag[i-1]!=i as the result. Here A[i]-1 and i-1 because the array is from 0 to n-1 to store 1 to n.
But the question requires that we can not use additional space. So we have to use the original array A, to save the flag. 
The idea is as follow:
e.g. 3,2,5,1,7
For each element,
1. Do not consider the element which <=0, or value > length n
2. Swap this element A[i] with the A[A[i]-1], e.g. when we met A[0]=3, we swap A[0] and A[2], then A[0]=5
3. For the current element A[i], if A[i]<=0 or A[i]>length n, or A[i] has already occurred, break. Else go to step 2.
    e.g. A[0]=5, swap A[0] and A[5], A[0]=7, break.Now the array A is {7,2,3,1,5}.
    Next round, A is {1,2,3,7,5}
4. Scan the array A and find the result. e.g. {1,2,3,7,5}, the A[3]!=3+1, print 3+1, result =4.

Source code:

class Solution {
    int firstMissingPositive(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        for (int i = 0; i<n;i++){
            if ( (A[i]>0)&&(A[i]<=n)){
                while (A[i]!=(i+1)){
                    if ((A[i]>n)||(A[i]<=0)||(A[A[i]-1]==A[i])) {break;}
                    int tmp;
                    tmp = A[A[i]-1];
        int i=0;
        for (; i<n;i++){
            if (A[i]!=(i+1)){
                return i+1;
        return i+1;


  1. 你好,我想和你讨论一下你的一行code

    while (A[i]!=(i+1)){
    if ((A[i]>n)||(A[i]<=0)||(A[A[i]-1]==A[i])) {break;}

    我的意思是,有了while (A[i]!=(i+1)),还需要(A[A[i]-1]==A[i]))吗?


    1. Hi there,
      I've checked the code again, and the 3rd condition in the "if " is required.
      As I said in the post (3rd point),"For the current element A[i], if A[i]<=0 or A[i]>length n, or A[i] has already occurred, break"

      The A[A[i]-1]==A[i] check if the element has already occurred.

      Also, A[i]==i+1 does not mean A[A[i]-1]==A[i], the first one check if the current element on the current position is correct, the second check if the current value has occurred. e.g.
      Let's say A=[1,1], i=1
      So, A[i]==i+1 --> A[1]==2 ---> 1==2 ---> false
      A[A[i]-1]==A[i] --> A[A[1]-1]==A[1] --> A[0]==A[1] --> 1==1 ---> true

      I want to also mention that you can have some modifications on the code to make it clearer, when you do that, pay attention to the starting case (A[0]), and the case that array has duplicate numbers.


  2. 谢谢你的详细解答,但我觉得这种情况是只有在array里有duplicate的时候才需要考虑
    A[] = {1,2,3,4,5,2}
    那么我们发现A[1]=2, 所以不必swap, break出来。


  3. btw, I want to say I really like your post on sorting algorithms. Very clear and informative!