Question: https://codility.com/demo/take-sample-test/prefix_set
Question Name: alpha2010 or PrefixSet
At the first glance, I think the set of Python is the best choice. Actually, the set solution passed all the test, and got 100/100 grade.
1 2 3 4 5 6 7 8 | def solution(A): alphabet = set() for element in A: alphabet.add(element) for index in xrange(len(A)): alphabet.discard(A[index]) if len(alphabet) == 0: return index |
BUT, acording to the time complexity provided by Python Wiki, in the worst case, the time complexity of set solution should be O(n^2). The key to improve is the statement: “each element of array A is an integer within the range [0..N−1]”. I have to admit, the official solution is much much more elegant.
1 2 3 4 5 6 7 8 | def solution(A): meet = [False]* len(A) result = -1 for index in xrange(len(A)): if meet[A[index]] == False: result = index meet[A[index]] = True return result |