An AC code costs more than constant space and may crash.


  • 0
    J

    This is an AC code. However it costs more than constant space and I can come up with an extreme case the code will crash.
    The idea is to store the candidate missing value in a hash table. Each individual operations, insertion and deletion, on a hash table costs constant time.
    When I try input data {0x7fffffff,1}, the program crashes. Luckily, the test case doesn't have such a case.

    public class Solution {
        public int firstMissingPositive(int[] A) {
            if ((A==null)||(A.length==0))
    		return 1;
    	int L = A.length;
    	int min = 0, max = 0;
    	for (int i=0; i<L; i++)
    		if (A[i]>0)
    		{
    			min = A[i];
    			break;
    		}
    	Set<Integer> st = new HashSet<Integer>();
    	for (int i=0; i<L; i++)
    	{
    		if (A[i]>max)
    		{
    			for (int j=max+1; j<A[i]; j++)
    				st.add(j);
    			max = A[i];
    		}
    		if ((A[i]<min)&&(A[i]>0))
    		{
    			for (int j=A[i]+1; j<min; j++)
    				st.add(j);
    			min = A[i];
    		}
    		if (A[i]>0)
    			st.remove(A[i]);
    	}
    	if (min>1)
    		return 1;
    	if (st.isEmpty())
    		return max+1;
    	min = 999;
    	for (Integer I : st)
    	{
    		if (min>I)
    			min = I;
    	}
    	return min;
        }
    }

Log in to reply
 

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