First missing positive

Question

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

        for(int i=0; i<=A.length; i++){
           if( (!myTable.containsKey(minVal-1)) && minVal-1>0){
                return minVal-1;
            }
            else if(!myTable.containsKey(minVal+1)){
                return minVal+1;
            }
            minVal++;
        }
        return minVal;
    }

Answer 1

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;
}

Answer 2

I guess it's quite good in 22 minutes.

1. Hashtable<Integer, Integer> myTable = new Hashtable<Integer, Integer>();
   

   Instead of the Hashtable use HashMap, but you use it like a Set (same key and value, so value is unused), so use a HashSet instead. See: Differences between HashMap and Hashtable?

2. I would use a longer variable names than A. Longer names would make the code more readable since readers don't have to decode the abbreviations every time and when they write/maintain the code don't have to guess which abbreviation the author uses. Furthermore, usual Java variable names are camelCase, with lowercase first letter. (See: Effective Java, 2nd edition, Item 56: Adhere to generally accepted naming conventions)

3. myTable could have a more descriptive name.

4. I've removed everything which does not change minVal's value:

   int minVal=0;
   ...
   for(int i : A){
       if(i<minVal && i>0){
           minVal = i;
       }
       ...
   }
   

   If I'm right the condition of the if statement is always false. If you substitute minVal's initial value, you get this:

   i < 0 && i > 0

   which is false, so minVal's value never can be changed.

5. I'd put a guard clause inside the for to get rid of the negative values and save some memory in the set:

   for (int i: A) {
       if (i < 0) {
           continue;
       }
       set.add(i);
   }
   

6. If you want to save some memory with big, non-repetitive input arrays you could use a new BitSet(A.length).

Answer 3

Re. the question, I take it that 0 isn't a positive integer? In an interview you might look for holes/ambiguities in the specification, and ask about them (double-check that you understand the requirements before coding).

Re. your code, on the plus side, well done for using a hash? Because a hash tends to be O(1) per lookup therefore O(n) overall.

I don't see how you can do better than O(n) because you need to look at every item.

On the minus side I think I see a simpler implementation, as follows (in pseudocode because I don't know Java):

public int firstMissingPositive(int[] A) {
{
    int length = A.Length;
    // create a vector of length 'length'
    Vector<bool> vector = new Vector<bool>(length);
    // this loop isn't necessary if Vector's elements are default-initialized (to false)
    for (int i = 0; i < length; ++i)
        vector[i] = false;
    // remember what the interesting input integers are
    foreach (a in A)
    {
        if (a > 0) && (a <= length)
            vector[a-1] = true;
        // else a is not a candidate
    }
    for (int i = 0; i < length; ++i)
    {
        if (!vector[i])
            // i+1 was not in the input array
            return i+1;
    }
    return length+1;
}

I think my solution is easier to read; and is probably faster and uses less memory (because I guess that Vector<boolean> is simpler and uses less space than HashSet<int>).

---

how you would judge it if I were to code this at a top-tier tech company for an interview

Assuming that one of the reasons for writing code in an interview is in order to give us something to talk about, to see how you respond to criticism, whether you can be guided to a better answer, whether you deeply understand the tools you choose to use, I might ask you whether you should specify the initialCapacity and loadFactor when you construct a HashSet, and what the effect of that would be; and drop some hints about whatever the best solution is (which as an interview I might already know 'unfairly' because I was looked it up in advance) to see whether you can get it.

Answer 4

One more implementation that I can think off using treeSet. Code is a bit easy to read and putting in some edge case checks to improve performance. This might not give a O(N) performance but would give O(Nlog N) as treeSet inserts are O(log N) for each insert. But the advantage is the retrieving of elements from treeSet.

public static int firstMissingPositive(int[] ip) {

    if (ip == null || ip.length == 0) {
        return 1;
    }

    TreeSet<Integer> postiveElements = new TreeSet<Integer>();

    for (int e : ip) {
        if (e > 0) {
            postiveElements.add(e);
        }
    }

    int tsSize = postiveElements.size();

    if (tsSize == 0 || postiveElements.first() > 1) {
        return 1;
    }

    if (tsSize == postiveElements.last()) {
        return tsSize+1;
    }


    int incElement = 1;

    for(; incElement <= tsSize; incElement++) {
        if (incElement != postiveElements.pollFirst()) {
            break;
        }
    }

    return incElement;
}