First missing positive As usual, please be brutally honest with your opinion of my code, and how you would judge it if I were to code this at a top-tier tech company for an interview(think Google, MSFT, Facebook, etc). My algorithm is has a worst time complexity of O(n).

Question:
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.* 


My code(coded in 22 minutes, with all test cases passed, devised initial algorithm in 2-5 minutes)

  public int firstMissingPositive(int[] A) {
        int minVal=0;
        if(A.length==0){
            return 1;
        }
        Hashtable&lt;Integer, Integer&gt; myTable = new Hashtable&lt;Integer, Integer&gt;();
        for(int i : A){
            if(i&lt;minVal &amp;&amp; i&gt;0){
                minVal = i;
            }
            myTable.put(i, i);
        }

        for(int i=0; i&lt;=A.length; i++){
           if( (!myTable.containsKey(minVal-1)) &amp;&amp; minVal-1&gt;0){
                return minVal-1;
            }
            else if(!myTable.containsKey(minVal+1)){
                return minVal+1;
            }
            minVal++;
        }
        return minVal;
    }
I have to disagree with palacsint about using HashMap, if anything, I think that you should use a Set implementation such as HashSet. You're never using the value that is stored in the map, and you have no reason to use it either. Therefore, I would go with a Set. (The fact that a HashSet internally uses a HashMap is an entirely different subject) Palacsint is correct though that HashMap is a better alternative than Hashtable.



Reading lines like this makes me sea-sick:

if( (!myTable.containsKey(minVal-1)) &amp;&amp; minVal-1&gt;0){


Use spacing properly and remove unnecessary parameters and it becomes:

if(!myTable.containsKey(minVal - 1) &amp;&amp; minVal - 1 &gt; 0) {




Overall, I think that you shouldn't need to use Objects for this (except an array of course, which technically is an object). I would only use primitives and use more self-documenting variable names.

An unnecessary operation in your code is that on each iteration you check containsKey twice. Once to see if value - 1 is set and once to see if value + 1 is set. Why not just check if value itself is set?

Your code can be rewritten and optimized into this: (This is a fixed version of ChrisW's approach, I had started the approach when he posted his answer and then I did some modifications to make sure it matched your code).

public int firstMissingPositive(int[] array) {
    boolean[] foundValues = new boolean[array.length];
    for (int i : array) {
        if (i &gt; 0 &amp;&amp; i &lt;= foundValues.length)
            foundValues[i - 1] = true;
    }

    for (int i = 0; i &lt; foundValues.length; i++) {
        if (!foundValues[i]) {
            return i + 1;
        }
    }
    return foundValues.length + 1;
}