Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

If the endpoint houses have different colors, their full span is optimal. Otherwise they share a color, and any valid interior pair has at least one house of a different color. Pair that house with the farther appropriate endpoint to obtain a distance at least as large. Thus some optimal pair uses an array endpoint.

Approach

Fix the last house and scan from the left until finding a different color, recording that distance. Then fix the first house and scan from the right for the farthest different color. Return the greater of the two distances. The input guarantees at least two colors, so a valid pair exists.

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        n = len(colors)
        d1, d2 = 0, 0
        l, r = 0, n - 1

        while l < r:
            if colors[l] != colors[r]:
                d1 = r - l
                break
            else:
                l += 1

        l, r = 0, n - 1

        while l < r:
            if colors[l] != colors[r]:
                d2 = r - l
                break
            else:
                r -= 1

        return max(d1, d2)

Complexity analysis

Let n = colors.length. Time: O(n) across the two inward scans. Auxiliary space: O(1).