I hope nobody have posted similar solution (it's tested, but I didn't submit it to contest):
from bisect import bisect_right as find def supernumbers(ls): indices = [0]*len(ls) for i, e in enumerate(ls): indices[e - 1] = i result = [None]*len(ls) borders = [] for i in indices: ind = find(borders, i) result[i] = ind + 1 if ind == len(borders): borders.append(i) else: borders[ind] = i return result At least, it looks shorter than other solutins. Of course, it allows number of optimizations like prefetching length and caching borders.append. If I'm correct, it takes O(n*log (max sequence length)) time that can be a win for huge datasets. With the best regards, anton. -- http://mail.python.org/mailman/listinfo/python-list