LeetCode 2078 - Two Furthest Houses With Different Colors

LeetCode Problem 2078

Difficulty: 🟢 Easy
Topics: Array, Greedy

Solution

Problem Understanding

The problem is asking us to find the maximum distance between two houses that have different colors. You are given a 0-indexed list colors where each element represents the color of a house. The distance between two houses at indices i and j is defined as abs(i - j) - the absolute difference of their indices.

The key here is to identify two houses with different colors that are as far apart as possible. The array is guaranteed to have at least two different colors, and the size of the array n ranges from 2 to 100, which is relatively small, but we can still optimize the solution.

Important edge cases include when the first and last house have the same color, or when the maximum distance occurs at the extremes of the array. Another consideration is arrays with only two houses, where the maximum distance is trivially 1 if the colors differ.

Approaches

Brute Force Approach

The brute-force approach would involve checking every pair of houses (i, j) where i < j, and calculating their distance if their colors differ. This ensures correctness because we literally check all possible pairs, but it is inefficient. For n houses, this requires O(n^2) comparisons, which is acceptable for small n but unnecessary when we can leverage observations.

Optimal Approach

The key insight is that the maximum distance will always involve one of the houses at either end of the array. Specifically, the furthest house with a different color than the first or last house will produce the maximum distance. This is because the distance function grows as the indices move apart. Therefore, we only need to compare the first house with houses from the end backward until a different color is found, and similarly for the last house with houses from the start forward.

This approach reduces the complexity from quadratic to linear, O(n), and requires only constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Compare all pairs of houses to find maximum distance with different colors
Optimal	O(n)	O(1)	Compare edges with opposite ends to find the maximum distance efficiently

Algorithm Walkthrough

1. Identify the color of the first house (colors[0]) and the last house (colors[-1]).
2. Starting from the last house and moving backward, find the first house whose color differs from colors[0]. Compute the distance to the first house.
3. Starting from the first house and moving forward, find the first house whose color differs from colors[-1]. Compute the distance to the last house.
4. Return the maximum of the two distances computed above.

Why it works: The furthest distance between two houses of different colors must involve one of the endpoints because moving closer to the middle always reduces distance. By checking only from the edges, we guarantee we find the maximum distance efficiently.

Python Solution

from typing import List

class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        n = len(colors)
        first_color = colors[0]
        last_color = colors[-1]

        # Maximum distance using first house
        max_dist_from_first = 0
        for i in range(n-1, -1, -1):
            if colors[i] != first_color:
                max_dist_from_first = i
                break

        # Maximum distance using last house
        max_dist_from_last = 0
        for i in range(n):
            if colors[i] != last_color:
                max_dist_from_last = n - 1 - i
                break

        return max(max_dist_from_first, max_dist_from_last)

The Python implementation defines two loops: one moving backward from the last house to find a color different from the first, and one moving forward from the first house to find a color different from the last. The result is the maximum of the two distances.

Go Solution

func maxDistance(colors []int) int {
    n := len(colors)
    firstColor := colors[0]
    lastColor := colors[n-1]

    maxDistFromFirst := 0
    for i := n-1; i >= 0; i-- {
        if colors[i] != firstColor {
            maxDistFromFirst = i
            break
        }
    }

    maxDistFromLast := 0
    for i := 0; i < n; i++ {
        if colors[i] != lastColor {
            maxDistFromLast = n - 1 - i
            break
        }
    }

    if maxDistFromFirst > maxDistFromLast {
        return maxDistFromFirst
    }
    return maxDistFromLast
}

In Go, slices are used similarly to Python lists. The loops are equivalent, and the distance computation subtracts the index from the last index where appropriate. Go does not require type hints but uses explicit indexing.

Worked Examples

Example 1

colors = [1,1,1,6,1,1,1]

Step	Index	Color	Action	Distance
Start	0	1	first_color = 1	-
End loop	6 → 3	1 → 6	colors[3] != first_color	max_dist_from_first = 3
Start loop	0 → 6	1 → 6	colors[3] != last_color	max_dist_from_last = 3
Return	-	-	max(3, 3)	3

Example 2

colors = [1,8,3,8,3]

Step	Index	Color	Action	Distance
first_color = 1	0	1	-	-
last_color = 3	4	3	-	-
Backward from end	4 → 0	3 → 1	colors[0] != 1	max_dist_from_first = 4
Forward from start	0 → 4	1 → 3	colors[4] != 3	max_dist_from_last = 4
Return	-	-	max(4,4)	4

Example 3

colors = [0,1]

Step	Index	Color	Action	Distance
first_color = 0	0	0	-	-
last_color = 1	1	1	-	-
Backward from end	1	1 != 0	max_dist_from_first = 1	-
Forward from start	0	0 != 1	max_dist_from_last = 1	-
Return	-	-	max(1,1)	1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Only two linear scans through the array are needed
Space	O(1)	Constant extra space for variables; no additional data structures

The linear scan ensures that each element is visited at most twice, giving O(n) time, and only a few integer variables are used, so space remains O(1).

Test Cases

# Provided examples
assert Solution().maxDistance([1,1,1,6,1,1,1]) == 3  # example 1
assert Solution().maxDistance([1,8,3,8,3]) == 4      # example 2
assert Solution().maxDistance([0,1]) == 1           # example 3

# Edge cases
assert Solution().maxDistance([1,2]) == 1           # minimal array
assert Solution().maxDistance([1,1,2]) == 2         # different color at the end
assert Solution().maxDistance([2,1,1,1]) == 3       # different color at the start
assert Solution().maxDistance([1,2,1,2,1,2]) == 5   # alternating colors
assert Solution().maxDistance([1,1,1,1,1,2]) == 5   # only last differs

Test	Why
[1,1,1,6,1,1,1]	Max distance in the middle
[1,8,3,8,3]	Max distance at array ends
[0,1]	Minimal array size
[1,2]	Minimal array with immediate difference
[1,1,2]	Different color at the end
[2,1,1,1]	Different color at the start
[1,2,1,2,1,2]	Alternating colors
[1,1,1,1,1,2]	Only last differs

Edge Cases

The first edge case occurs when the array has only two elements. This is trivial but must return 1 if the colors differ, otherwise zero. The second case is when all elements are the same except the last one. The algorithm handles this by scanning backward from the end and finding the differing color immediately. The third edge case is when the differing