KeiruaProd

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
        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.