Problem Statement in English

You’re given an array colors where colors[i] is the color of the i-th house. Return the maximum distance between two houses with different colors.

Approach

Since the question guarantees that there are at least two different colors, we can simply check the distance of the first and last house with a different color from the first and last house respectively.

The maximum of these two distances will be our answer.

And we’re done!

Solution in Python


class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        n = len(colors)
        res = 0
        
        for i in range(n):
            if colors[0] != colors[i]:
                res = max(res, i)
            if colors[-1] != colors[i]:
                res = max(res, n - i -1)
                
        return res

Complexity

  • Time: $O(n)$
    Since we traverse the array once.

  • Space: $O(1)$
    Since we are using only a constant amount of space.

And we are done.