First missing integer in an unsorted array

Problem statement – Given an unsorted integer array, find the first missing positive integer. Example,

• If A = [-1, 4, 2, 3, 5], missing integer = 1.
• If A = [1, 5, 2, 3, 4, 7], missing integer = 6.
• If A = [-1, -2, -3, -4], missing integer = 1.

Clues –

• Your solution should be O(N) in time and O(1) in space.
• Can you make changes in the array such that you can mark which numbers in 1 to N are already present in the array?

Solution – This is a little difficult one, so pay attention! If you go through the problem statement carefully, your solution will be an integer between 1 to N + 1, where N is the size of the array. Why N + 1? If the array had all integers from 1 to N, then the missing integer would be N + 1!

Now that we know our solution will be an integer from 1 to N + 1, we need to come up with a mechanism to mark/flag the numbers in 1 to N + 1, which are already present in the array. If we could use O(N) space, then we could create a boolean array isPresent[] of size N + 1, and set isPresent[A[i]] = true. The solution would be something like this –

boolean[] isPresent = new boolean[N + 1];

for (int i = 0; i < A.length; ++i) {
    isPresent[A[i]] = true;
}

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

return N + 1;

But since our solution should be O(1) in space, we need to do this marking in our input array itself. Can we take advantage of the fact that the indices of an array is a contiguous span of numbers from 1 to N? Yes!

We will do this by making numbers at certain indexes negative. The idea is that, let’s say, we have A[i] = 3, then we will make A[3] negative. So that, when we make another scan of the array A, and we see A[3] is negative, we know that 3 has occurred somewhere in the array. Read the previous sentence once more, let it sink in. Now let’s write it as a formula –

int value = A[i];
A[value] = -A[value];

Now the question is, what if A[i] is negative? Let’s handle that case in our newly born formula.

int value = Math.abs(A[i]);
A[value] = -A[value];

Now the question is, what if A[value] is already negative? Let’s handle that case in our formula –

int value = Math.abs(A[i]);
A[value] = -Math.abs(A[value]);

So we will apply this formula to all the elements in the array by iterating over the whole array. Now, we will make another iteration over the array. If at any index i, we get A[i] as positive, then it means that the integer i was not present in the input array, otherwise A[i] would have been negative! So integer i is our missing integer. Read the solution again if you didn’t understand it in the first reading (I didn’t either 😛 )

Before you race off to code, there are a couple of issues we must handle. Firstly, what if we have negative integers or integers greater than N in our array? We know that our solution will be an integer between 1 and N + 1, so any other integer is junk for us. So we can replace all of them with a constant, say a variable called FLAG. So, when we encounter them in our formula loop, we can ignore them. Now keep in mind that they might have become negative because of some other element in the array. So, in our formula loop, we must ignore elements with values FLAG and -FLAG.

Secondly, up until now, for the sake of simplicity we spoke in terms of 1 indexed arrays, but we know that in real code, we have 0 indexed arrays. I guess you can handle that 😉

Code –

public class Solution {
	public int firstMissingPositive(ArrayList<Integer> a) {
	    final int N = a.size();     // size
	    // a dummy value to replace
	    // integers below 0 and above N
	    final int FLAG = N + 2; 
	    
	    for (int i = 0; i < N; ++i) {
	        if (a.get(i) <= 0 || a.get(i) > N) {
	            a.set(i, FLAG);
	        }
	    }
	    
	    // Our formula loop
	    for (int i = 0; i < N; ++i) {
	        if (a.get(i) == FLAG || a.get(i) == -FLAG) {
	            continue;
	        }
	        
	        int value = Math.abs(a.get(i));
	            
	        a.set(value - 1, -Math.abs(a.get(value - 1)));
	    }
	    
	    // Loop through collection. Whichever
	    // index holds a +ve integer is the answer
	    for (int i = 0; i < N; ++i) { if (a.get(i) > 0) {
	            return i + 1;
	        }
	    }
	    
	    // If the collection has all integers
	    // from 1 to N, then answer is N + 1
	    return N + 1;
	}
}