Codility Iota 2011: https://codility.com/c/intro/demoTDTEB9-GS3

iota.cpp

/*
 * The difficult part about this problem was figuring out it was
 * only BFS. The restrictions of time O(nlogn) and space O(n) 
 * were easy to figure out.
 */

#include <algorithm>
#include <queue>
#include <utility>
#include <iostream>
#include <map>

using namespace std;

typedef pair<int,int> pi;

int binarySearch(const vector<pi> &sorted, int target) {
    int start = 0,
        end = sorted.size()-1,
        half = 0;

    while (start <= end) {
        half = start + (end-start)/2;

        if (sorted[half].first == target) break;

        if (sorted[half].first < target) {
            start = half+1;
        } else {
            end = half-1;
        }
    }

    //Ensures we get to the very start if there are more than one
    while (half >= 0 && sorted[half].first == target) {
        half--;
    }

    return half+1;
}

int solution(const vector<int> &A) {
    vector<pi> sorted(A.size());
    map<int,int> levels;
    queue<int> bfs;
    int index = 0,
        indices = 0,
        level = 0;

    //O(n)
    for (int i=0; i < A.size(); i++) {
        sorted[i] = pi(A[i], i);
    }

    //O(nlogn)
    sort(sorted.begin(), sorted.end());
    
    indices = binarySearch(sorted, A[0]);
    for (int i=indices; sorted[i].first == A[0]; i++) {
        levels[sorted[i].second] = 1;
        bfs.push(sorted[i].second);
    }

    //O(nlogn)
    while (!bfs.empty()) {
        index = bfs.front();
        level = levels[index];
        bfs.pop();

        if (index == A.size()-1) {
            return levels[index];
        }

        if (index < A.size()-1 && !levels[index+1]) {
            indices = binarySearch(sorted, A[index+1]);
            for (int i=indices; sorted[i].first == A[index+1]; i++) {
                levels[sorted[i].second] = level+1;
                bfs.push(sorted[i].second);
            }
        }

        if (index > 0 && !levels[index-1]) {
            indices = binarySearch(sorted, A[index-1]);
            for (int i=indices; sorted[i].first == A[index-1]; i++) {
                levels[sorted[i].second] = level+1;
                bfs.push(sorted[i].second);
            }
        }
    }

    return -1;
}