First missing positive with only primitives

As soon as I saw the First missing positive question, I decided to write my own method for this before writing my review on the question.

Judge me by the same standards as bazang wants to be judged, i.e. As if this was written for a big company such as Google for an interview.

I wasn’t sure how the input 7, 8, 9 should be treated so to make it a bit harder for myself I gave myself the requirement that it should return 10.

@Test
public void test() {
    Assert.assertEquals(3, missingInt(new int[]{ 1, 2, 0 }));
    Assert.assertEquals(4, missingInt(new int[]{ 1, 2, 3 }));
    Assert.assertEquals(2, missingInt(new int[]{ 3, 4, -1, 1 }));
    Assert.assertEquals(10, missingInt(new int[]{ 7, 8, 9 }));

    Assert.assertEquals(5, missingInt(new int[]{ 3, 4, 2, 7, 6, 1 }));
    Assert.assertEquals(5, missingInt(new int[]{ 3, 4, 2, 7, 6, 1, -4 }));
}


public int missingInt(int[] array) {
    boolean[] foundIntegers = new boolean[array.length];
    int smallestPositive = Integer.MAX_VALUE;

    for (int i : array) {
        if (i > 0 && i < smallestPositive)
            smallestPositive = i;
    }

    for (int i : array) {
        if (i < smallestPositive)
            continue;

        int index = i - smallestPositive;
        if (index < foundIntegers.length)
            foundIntegers[index] = true;
    }

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

Answer

That solution is the algorithm I would have chosen.

I like the data you chose for your list of test cases; you could have added at least one more test case, i.e. an input array with zero elements.

In fact IMO your code will fail when the input is a zero-length array.

You code will also fail when all the input integers are <= 0.

Attribution
Source : Link , Question Author : Simon Forsberg , Answer Author : ChrisW

Leave a Comment