2078. Two Furthest Houses With Different Colors

Array
Greedy

TIME

O(n)

SPACE

O(1)

Intuition

To maximize distance, one endpoint must be either the first house (index 0) or the last house (index n-1). Check both scenarios.

Solution

From house 0, find the furthest house with a different color (scan from end)
From house n-1, find the furthest house with a different color (scan from start)
Return the maximum of these two distances

n = len(colors)
dist = 0

# Check from first house
for j in range(n - 1, -1, -1):
    if colors[j] != colors[0]:
        dist = max(dist, j)
        break

# Check from last house
for i in range(n):
    if colors[i] != colors[n - 1]:
        dist = max(dist, n - 1 - i)
        break

Complexity

Time: O(n)
Space: O(1)

Edge Cases

Two houses with different colors
All same color except endpoints
Alternating colors

Code

from typing import List


class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        """
        2078. Two Furthest Houses With Different Colors
        Time: O(n)
        Space: O(1)
        """
        n = len(colors)
        dist = 0

        # Check from first house - find furthest different color
        for j in range(n - 1, -1, -1):
            if colors[j] != colors[0]:
                dist = max(dist, j)
                break

        # Check from last house - find furthest different color
        for i in range(n):
            if colors[i] != colors[n - 1]:
                dist = max(dist, n - 1 - i)
                break

        return dist

/**
 * 2078. Two Furthest Houses With Different Colors
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        int dist = 0;

        // Check from first house - find furthest different color
        for (int j = n - 1; j >= 0; j--) {
            if (colors[j] != colors[0]) {
                dist = Math.max(dist, j);
                break;
            }
        }

        // Check from last house - find furthest different color
        for (int i = 0; i < n; i++) {
            if (colors[i] != colors[n - 1]) {
                dist = Math.max(dist, n - 1 - i);
                break;
            }
        }

        return dist;
    }
}