Two Furthest Houses With Different Colors

easy greedy array two pointers

Problem

There are n houses in a row, painted with colors given by a 0-indexed array colors. Return the maximum distance between two houses with different colors, where the distance between houses i and j is abs(i - j).

Inputcolors = [1,1,1,6,1,1,1]

Output3

House 0 (color 1) and house 3 (color 6) differ; distance abs(0 - 3) = 3. Houses 3 and 6 also give 3.

Inputcolors = [1,8,3,8,3]

Output4

House 0 (color 1) and house 4 (color 3) differ; distance abs(0 - 4) = 4.

colors (comma-separated)

def maxDistance(colors):
    n = len(colors)
    best = 0
    for i in range(n):
        if colors[i] != colors[0]:
            best = max(best, i)
        if colors[i] != colors[n - 1]:
            best = max(best, n - 1 - i)
    return best

function maxDistance(colors) {
  const n = colors.length;
  let best = 0;
  for (let i = 0; i < n; i++) {
    if (colors[i] !== colors[0])
      best = Math.max(best, i);
    if (colors[i] !== colors[n - 1])
      best = Math.max(best, n - 1 - i);
  }
  return best;
}

int maxDistance(int[] colors) {
    int n = colors.length;
    int best = 0;
    for (int i = 0; i < n; i++) {
        if (colors[i] != colors[0])
            best = Math.max(best, i);
        if (colors[i] != colors[n - 1])
            best = Math.max(best, n - 1 - i);
    }
    return best;
}

int maxDistance(vector<int>& colors) {
    int n = colors.size();
    int best = 0;
    for (int i = 0; i < n; i++) {
        if (colors[i] != colors[0])
            best = max(best, i);
        if (colors[i] != colors[n - 1])
            best = max(best, n - 1 - i);
    }
    return best;
}

Explanation

The key greedy insight: in any optimal answer, at least one of the two chosen houses is an endpoint — either the first house (index 0) or the last house (index n - 1).

Why? Suppose the best pair is (i, j) with i < j and neither is an endpoint. If colors[0] differs from colors[j], the pair (0, j) is at least as far. Otherwise colors[0] == colors[j], so colors[0] differs from colors[i], and (0, i) spans at least as much... a symmetric argument anchors the other side to n - 1. So an endpoint is always good enough.

That collapses the problem to a single pass. For each index i we ask two questions: does house i differ from the left endpoint? If so it could pair with index 0 for distance i. Does it differ from the right endpoint? If so it could pair with index n - 1 for distance n - 1 - i.

We keep the running maximum best over both candidate distances. Because the data guarantees at least two different colors exist, best ends strictly positive.

This runs in O(n) time and O(1) extra space — a single sweep, no sorting, no nested loops.

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