3 Responses

  1. Yuan Yao
    Yuan Yao November 6, 2012 at 9:54 pm |

    First, this problem says “constant space.”
    And your “char arr[size]” is definitely not constant.
    Second, you don’t need to find the max of the array.
    Let’s say array [-1,1,2,1000000,6], do we need 1000000 bits?
    no, because the array size is only 5, so the first missing positive integer is at most 6.
    Here’s my code:

    public class Solution {
    public int firstMissingPositive(int[] A) {
    int[] check = new int[A.length];
    for(int i=0;i<A.length;i++){
    if(A[i]A.length){
    continue;
    }else{
    check[A[i]-1]=1;
    }
    }
    for(int i=0;i<check.length;i++){
    if(check[i]==0){
    return i+1;
    }
    }
    return check.length+1;
    }
    }

    But sitll, it's not constant space. I am wondering if there's a constant space solution.

    Reply
  2. Yuan Yao
    Yuan Yao November 6, 2012 at 10:00 pm |

    Sorry , the body of the first for loop should be :

    if(A[i]A.length){
    continue;
    }else{
    check[A[i]-1]=1;
    }

    I copy & paste it by mistake.

    Reply

Leave a Reply