Using V[i:j] to represent items i through j of the vector (not i though j-1 as in Python), I think you want to find i and j such that j-1 is maximized and the number of distinct entries is k (because if it were less than k, you could increase j or decrease i). My naive thought would be to start with i=1, j=k and make a table (kx2) with the distinct entries of V in the first column and the count in the current interval in the second. If you don't have k distinct entries, keep adding to j, updating the table, until you do. Record i and j as the best seen yet. Then increase i to 2, updating your table, and see if you can increase j. Continue through V, at each step seeing if the gap has increased. If so, replace the stored best so far i and j. I don't think this is worse than O(nk)-the original sort is k ln k, and you make only one pass through the n items. For each new item, you might have to look through k lines in the table once or twice, but it shouldn't be k^2. Does that work?