Codility 'FrogRiverOne' Solution

Martin Kysel · May 20, 2014

Short Problem Definition:

Find the earliest time when a frog can jump to the other side of a river.



expected worst-case time complexity is O(N)

expected worst-case space complexity is O(X)


Mark seen elements as such in a boolean array. I do not like the idea of returning the first second as 0. But specifications are specifications :)


def solution(X, A):
    passable = [False] * X
    uncovered = X

    for idx in xrange(len(A)):
        if A[idx] <= 0 or A[idx] > X:
            raise Exception("Invalid value", A[idx])
        if passable[A[idx]-1] == False:
            passable[A[idx]-1] = True
            uncovered -= 1
            if uncovered == 0:
                return idx

    return -1

Twitter, Facebook