Two Furthest Houses With Different Colors

Intuition

We need the largest distance between two indices whose colors are different.

The distance between houses i and j is:

abs(i - j)

Since we can always choose the smaller index first, every pair can be written as:

left < right

Then the distance becomes:

right - left

So the most direct idea is to check every pair of houses and keep the biggest valid distance.

Approach: Enumeration

We use two loops:

1. Pick the first house using left
2. Pick every house to its right using right
3. If colors[left] != colors[right], the pair is valid
4. Update the answer with right - left

The constraints are small, with n <= 100, so checking all pairs is completely fine.

The problem also guarantees that at least two houses have different colors, so a valid answer always exists.

class Solution {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        int answer = 0;

        for (int left = 0; left < n; left++) {
            for (int right = left + 1; right < n; right++) {
                if (colors[left] != colors[right]) {
                    answer = Math.max(answer, right - left);
                }
            }
        }

        return answer;
    }
}

Dry run

Take:

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

We try pairs from left to right.

For house 0:

• house 1 has the same color, skip
• house 2 has the same color, skip
• house 3 has a different color, distance = 3 - 0 = 3
• house 4, 5, and 6 have the same color as house 0, skip

So far, the best answer is 3.

Later, house 3 and house 6 also have different colors:

6 - 3 = 3

No pair gives a larger distance, so the final answer is 3.

Why this works

The answer must be formed by some pair of houses with different colors.

The nested loops check every possible pair exactly once:

• if the colors are the same, that pair cannot be the answer
• if the colors are different, we compute its distance

Since every valid pair is considered and we always keep the maximum distance, the final value is the largest possible distance.

Complexity Analysis

Time Complexity: O(n^2)

• we enumerate all pairs of houses

Space Complexity: O(1)

• we only store the answer and loop variables