Codility Challenge: Alpha (C++)

So the first challenge Codility gives to us is a very simple one, but nonetheless I have often seen people take a naive approach to similar problems.

You are given a sequence of elements, and the task is to find the first index at which point there are no elements beyond it that haven't been seen in the previous elements (including the one at that index).

To see the full description of the challenge (and attempt it if you like), here it is.

One naive approach would be this:

int solution(vector<int> &A) {
    int index = 0;
    for(unsigned int i = 0; i < A.size(); ++i){
        bool seen = false;
        for(unsigned int j = 0; j < i; ++j){
            if(A[i] == A[j]){
                seen = true;
                break;
            }
        }
        if(!seen){
            index = i;
        }
    }
    return index;
}

It determines whether element i has been seen or not be looping through all the elements before it and setting the index to return as i if it doesn't finds a match. By the time it gets to the end of the outer loop, the last index that was assigned will be the solution as no indices beyond that stored new elements. This certainly works but has a couple of major problems:

• For such a simple problem, a nested loop is pretty intense and has left us with some messy code
• We are making comparisons to the same elements over and over again meaning our solution is very slow

It is very easy to fix both problems by storing the elements we have already checked in an unordered set. This will give us a 'golden' solution with O(N) (linear) time complexity:

#include <unordered_set>  

int solution(vector<int> &A){  
    int index = 0;  
    unordered_set<int> values;  

    for(unsigned int i = 0; i < A.size(); ++i){  
        if(values.insert(A[i]).second){  
            index = i;  
        }  
    }  
    return index;  
}  

The reason this way is so much faster is that unordered_sets use hash tables which enable them to have an average time complexity of O(1) when it comes to element lookups.

The way we are checking whether the element has been seen before is using the return value of unordered_set::insert which gives us a pair of values:

1. An iterator pointing to the element that was inserted (or to an element of the same value if it was already inserted)
2. A boolean telling us whether the value was inserted or not.

If the second value is true, we know that the element hasn't been seen before, otherwise it would already be in the unordered set and the insert would have been unsuccessful. Using this, we can do both the insert and the check in the same statement. Great!

Something that bothers me is that very often when I see similar problems taken on, a solution almost the same as our golden solution is used except it uses a 'common' data structure like another vector or array which uses some sort of linear storage. At next to no difference in effort writing it, this solution would be much slower as it would need to loop through this structure making it, performance wise, very similar to our original naive approach.

The main lesson from this is using a sensible data structure. When we are checking the previous elements in this problem there are some things we don't care about like:

• The order they were in
• The indices they were at
• How many of them were there

 which a structure like a vector may have been useful for, and there are some things we do care about:

• Whether element i was there or not
• That's it 

 Which made our unordered set an ideal candidate for this role. A little thought into what you really need can go a long way in algorithm design.