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:

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.