Matthis Hammel shared this problem recently:
In a street with colored houses, you want to take a picture containing the most houses, but without any duplicate colors. In other words: find the longest possible sub-array containing only unique values. If several options exist, you can return any of them. Hint (only if you're stuck): https://stackoverflow.com/questions/8269916
It comes with some unit tests, and a sample, very slow
O(n^2) implementation. How can we turn it into an
O(n) implementation ?
The solution (as you can see in the heavily documented hint, well worth a read) is to use the
sliding window technique.
The core idea of this technique is to navigate the list while keeping track of two indices,
end. Between those two indices, you ensure that the list always has different colors.
end index moves, there is a color in its associated house:
setof seen colors. The
startindex will not move.
startindex until the invariant is ensured.
This is maybe easier with read python code:
def longest_unique_sublist(colors): """ Find the longest sublist where all the values are different, in O(n) """ seen = set() start = 0 best_start, best_end = 0, 0 # on to the sliding window for end, color in enumerate(colors): while color in seen: seen.remove(colors[start]) start += 1 seen.add(color) if end - start > best_end - best_start: best_start, best_end = start, end return colors[best_start:best_end+1]
That was pretty fun.