Issues of my Codility example test solution

The question was Write a function:

class Solution { public int solution(int[] A); } that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1. Assume that:

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000..1,000,000]. Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

public static int solution(int[] A) { int min = 1; boolean negArray = true; for(int i = 0; i < A.length; i++) { if(A[i] > 0) { negArray = false; if(A[i] < min) { min = A[i]; } } } int i = 1; while(contains(A, min+i)) { i++; } if(negArray || A.length <= 0) return 1; return min + i; } public static boolean contains(int[] A, int x) { for(int i = 0; i < A.length; i++) { if(A[i] == x) return true; } return false; } 

This was my solution and I got 25% correctness. I would like to know what I did wrong.

2 Answers

You can simplify the problem down by recognizing that you just need to keep track of the integers you've seen in array that your given. You also need to account for edge cases for when the array is empty or the value you get would be greater than your max allowed value. Finally, you need to ensure O(n) complexity, you can't keep looping for every value you come across. This is where the boolean array comes in handy. See below -

public static int solution(int[] A) { int min = 1; int max = 100000; boolean[] vals = new boolean[max+1]; if(A.length == 0) return min; //mark the vals array with the integers we have seen in the A[] for(int i = 0; i < A.length; i++) { if(A[i] < max + 1) vals[A[i]] = true; } //start at our min val and loop until we come across a value we have not seen in A[] for (int i = 1; i < max; i++) { if(vals[i] && min == i) min++; else if(!vals[i]) break; } if(min > max) return max; return min; } 

The worst case for looping is A.length + max which is O(N)

This is my 100% solution for it on javascript:

function solution(A) { // write your code in JavaScript (Node.js 8.9.4) A.sort((a, b) => a - b); let smallestPositive = 1; for (let i = 0; i < A.length; i++) { const currentInteger = A[i]; if (currentInteger > 0 && currentInteger === smallestPositive) { smallestPositive = smallestPositive + 1; } else if (currentInteger > smallestPositive) { return smallestPositive; } } return smallestPositive; } 

You start a counter with 1 (since is smallest positive integer)

Then if you sort the array you can just traverse it, and after you find the first positive number you compare the values with this counter that is increased if the current value is equal. Otherwise you return the counter.

I recently did all codility tasks on javascript, all with 100% and this might help someone if you are stuck