Codility Prefix Set

In this article I will provide a solution to the Prefix Set sample Codility problem. The problem description is copyrighted, so have a look at the link for the description. The gist of the problem is:

Given an integer array \(A\), return the smallest index \(P\) such that the subarray \([0,P]\) includes all the elements from the whole array \(A\).

This is not too difficult. I will use a Set data structure to keep track of the numbers that I still haven’t visited. At the beginning, run through the whole array and add all the numbers to the set. Then, traverse the array, and remove the number you are currently looking at from the set. If the set becomes empty, you’ve found your prefix set.

The Java code that scores 100/100 might look like this:

public static int coveringPrefix(int[] A){
    Set<Integer> s = new HashSet<Integer>();
    for(int i : A) s.add(i);
    for(int i = 0; i < A.length; i++){
        s.remove(A[i]);
    if(s.isEmpty()) return i;
    }
    return 0;
}

Alternatively, we can do without using any specialized data structures, and just use an array of booleans to keep track of the numbers seen so far. The code is longer, but doesn’t use any special data structures, and still scores 100/100:

public static int coveringPrefixNoSet(int[] A){
    boolean[] bools = new boolean[A.length];
    int unique = 0;
    for(int i = 0; i < A.length; i++){
      if(!bools[A[i]]){
        bools[A[i]] = true;
        unique++;
      }
    }
    for(int i = 0; i < A.length; i++){
      if(bools[A[i]]){
        bools[A[i]] = false;
        unique--;
        if(unique == 0){
          return i;
        }
      }
    }
    return 0;
}