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 myTable = new Hashtable();
        for(int i : A){
            if(i0){
                minVal = i;
            }
            myTable.put(i, i);
        }

        for(int i=0; i0){
                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)) && minVal-1>0){

Use spacing properly and remove unnecessary parameters and it becomes:

if(!myTable.containsKey(minVal - 1) && minVal - 1 > 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 > 0 && i <= foundValues.length)
            foundValues[i - 1] = true;
    }

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

StackExchange Code Review Q#43813, answer score: 8