Find the smallest positive integer that does not occur in a given sequence

Question

I was trying to solve this problem:

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).

I wrote the solution below which gives a low performance, however, I can't see the bug.

public static int solution(int[] A) {

        Set<Integer> set = new TreeSet<>();

        for (int a : A) {
            set.add(a);
        }

        int N = set.size();

        int[] C = new int[N];

        int index = 0;

        for (int a : set) {
            C[index++] = a;
        }

        for (int i = 0; i < N; i++) {

            if (C[i] > 0 && C[i] <= N) {
                C[i] = 0;
            }
        }

        for (int i = 0; i < N; i++) {

            if (C[i] != 0) {
                return (i + 1);
            }
        }

        return (N + 1);
    }

The score is provided here,

I will keep investigating myself, but please inform me if you can see better.

Answer 1

If the expected running time should be linear, you can't use a TreeSet, which sorts the input and therefore requires O(NlogN). Therefore you should use a HashSet, which requires O(N) time to add N elements.

Besides, you don't need 4 loops. It's sufficient to add all the positive input elements to a HashSet (first loop) and then find the first positive integer not in that Set (second loop).

int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        return i;
    }
}

Answer 2

100% result solution in Javascript:

function solution(A) {
    // only positive values, sorted
    A = A.filter(x => x >= 1).sort((a, b) => a - b)

    let x = 1

    for(let i = 0; i < A.length; i++) {
        // if we find a smaller number no need to continue, cause the array is sorted
        if(x < A[i]) {
            return x
        }
        x = A[i] + 1
    }

    return x
}

Answer 3

My code in Java, 100% result in Codility

import java.util.*;

class Solution {
    public int solution(int[] arr) {

        Arrays.sort(arr);

        int smallest = 1;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == smallest) {
                smallest++;
            }
        }

        return smallest;
    }
}