374. Two Furthest Houses With Different Colors

Try every pair (i, j) and keep the maximum j - i whenever the colors differ.

Approach

1. For each i from 0 to n - 1:
   • For each j from i + 1 to n - 1:
     • If colors[i] != colors[j], update the answer with j - i.
2. Return the maximum.

Complexity

• Time: O(n²).
• Space: O(1).

import java.util.*;

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

The optimal pair must include either house 0 or house n - 1 — never some interior pair. Once you believe that, the algorithm is two simple linear scans.

Why must the answer touch an endpoint?

Suppose the optimal pair is (i*, j*) with colors[i*] != colors[j*], and that neither endpoint is involved (so 0 < i* < j* < n - 1). We will show a pair using an endpoint is at least as long.

colors[0] is either equal to colors[i*] or equal to colors[j*] — but not both, because colors[i*] != colors[j*].

• Case A: colors[0] != colors[j*]. Then the pair (0, j*) is valid and has distance j* - 0 = j*, which is strictly greater than j* - i*. Better.
• Case B: colors[0] != colors[i*]. Then by the same reasoning, the pair (0, i*)'s mirror argument with n - 1 works: colors[n - 1] differs from at least one of colors[i*], colors[j*], and pairing n - 1 with that index gives a longer or equal distance.

So we never lose by anchoring on an endpoint.

Steps

1. Anchor on house 0: walk from the right end leftwards. Find the largest j such that colors[j] != colors[0]. The candidate distance is j.
2. Anchor on house n - 1: walk from the left end rightwards. Find the smallest i such that colors[i] != colors[n - 1]. The candidate distance is n - 1 - i.
3. Return the larger of the two candidates.

Walk-through

colors = [1, 8, 3, 8, 3], n = 5.

Anchor on house 0 (color 1):

• j = 4: colors[4] = 3 != 1 → match. Distance 4. Stop.

Anchor on house n-1 (color 3):

• i = 0: colors[0] = 1 != 3 → match. Distance 4. Stop.

Answer: max(4, 4) = 4. ✓

Another example, colors = [1, 1, 1, 6, 1, 1, 1]:

• Anchor on house 0 (color 1): walk from right. colors[6]=1, colors[5]=1, colors[4]=1, colors[3]=6 != 1 → distance 3.
• Anchor on house 6 (color 1): walk from left. colors[0]=1, colors[1]=1, colors[2]=1, colors[3]=6 != 1 → distance 6 - 3 = 3.

Answer: 3.

Edge case

The problem guarantees at least two houses have different colors, so each scan finds a match — no special-case for "no answer".

Complexity

• Time: O(n) — at most two passes, and each scan stops as soon as it finds a mismatch.
• Space: O(1).