# KeiruaProd

I help my clients acquire new users and make more money with their web businesses. I have ten years of experience with SaaS projects. If that’s something you need help with, we should get in touch!
< Back to article list

## The street picture problem

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, `start` and `end`. Between those two indices, you ensure that the list always has different colors.

When the `end` index moves, there is a color in its associated house:

• if this color has not been seen yet, we can add it to a `set` of seen colors. The `start` index will not move.
• if this color has been seen, we have to move `start` index 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