Java Solution to Codility’s Missing Integer Problem

June 27, 2018

Hey Developer,

I am bringing you another high quality Java solution. This time, I am solving the Missing Integer problem which can be found here.

My solution has runtime of O(N) and space complexity of O(N) as I am using a second array to solve the problem. The key to solving this problem is to realize that the only integers that matter in A are in the range [1, N].

Explanation:

1. Create a boolean array B the same size as the input array A and pretend that the array index starts at 1 (for simplicity).
2. Iterate through array A and every time you encounter a value in the range [1, N] mark it as true in the boolean array B
3. Iterate through array B and when you encounter a false value, return that index
4. If you get through B without encountering a false value, then return N+1

I hope this graphic helps you understand the concept, because it took me way too long to make. Ha-ha.

Below is the code for my Java solution.

class Solution {
	public int solution(int[] A) {
	// variable representing the number of elements in A
	int A_N = A.length;
	// boolean array that represents the smallest positive values in A
	// size is A_N + 1 because I am not using index 0 for simplicity
	boolean [] B = new boolean[A_N + 1];
	// variable representing the number of elements in B
	int B_N = B.length;
 
	// iterate through A and update B accordingly 
	for (int i = 0; i < A_N; i++) {
	// if a value is greater than 0 (since we only care about positive values)
	// AND if value is within B's range 
		if (A[i] > 0 && A[i] < B_N) {
			// update B to show that A contains that number
			B[A[i]] = true;
		}	
	}
	// iterate through Boolean array B
	for (int i = 1; i < B_N ; i++) {
		// return the first value in B that is false
		if (B[i] == false) {
			return i;
		}
	}
 
	// if all of the values inside B are true(except 0), then we return the next biggest integer
	return B_N;
    }
}